<repo_name>khonthai/Algorithms<file_sep>/evacuation_plan.cpp
#include<stdio.h>
#include<vector>
#include<math.h>
using namespace std;
#define MAX_N 100
#define MAX_M 100
#define MAX_V 202
#define INF 1e9
#define MAX_E 10200
struct edge{
    int to, cap, cost, rev;
};
vector<edge> G[MAX_V];
int dist[MAX_V];
int prevv[MAX_V];
int preve[MAX_E];
int v;

int X[MAX_N], Y[MAX_N], B[MAX_N];
int P[MAX_M], Q[MAX_M], C[MAX_M];
int E[MAX_N][MAX_M];

void add_edge(int from, int to, int cap, int cost){
    G[from].push_back((edge) {to, cap, cost, G[to].size()});
    G[to].push_back((edge){from, 0, -cost, G[from].size()-1});
}

int min_cost_flow(int s, int t, int f){
    int res = 0;
    while (f > 0) {
        bool update = true;
        fill(dist, dist+v, INF);
        dist[s] = 0;
        while (update == true) {
            update = false;
            for (int i = 0 ; i < v; i++) {
                for (int j = 0; j < G[i].size(); j++) {
                    edge &ed = G[i][j];
                    if (ed.cap > 0 && dist[i]+ed.cost < dist[ed.to]) {
                        dist[ed.to] = dist[i]+ed.cost;
                        prevv[ed.to] = i;
                        preve[ed.to] = j;
                        update = true;
                    }
                }
            }
        }
        if (dist[t] == INF) {
            return -1;
        }
        int d = f;
        for (int i = t; i != s; i = prevv[i]) {
            d = min(d, G[prevv[i]][preve[i]].cap);
        }
        f -= d;
        res += d*dist[t];
        for (int i = t; i != s; i = prevv[i]) {
            edge &ed = G[prevv[i]][preve[i]];
            ed.cap -= d;
            G[i][ed.rev].cap += d;
        }
    }
    return res;
}

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    v = n+m+2;
    int f = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d %d %d", &X[i], &Y[i], &B[i]);
        add_edge(0, i+1, B[i], 0);
        f += B[i];
    }
    for (int i = 0; i < m; i++) {
        scanf("%d %d %d", &P[i], &Q[i], &C[i]);
        add_edge(n+1+i, n+m+1, C[i], 0);
    }
    int sum = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int c = sqrt((P[j]-X[i])*(P[j]-X[i])+(Q[j]-Y[i])*(Q[j]-Y[i]));
            add_edge(i+1, n+1+j,INF, c);
            scanf("%d", &E[i][j]);
            sum += E[i][j]*c;
        }
    }
    int lowest = min_cost_flow(0, n+m+1, f);
    if (sum == f) {
        printf("OPTIMAL\n");
    }else{
        printf("SUBOPTIMAL\n");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                printf("%d%c", G[n+1+j][i+1].cap, j+1 == m? '\n' : ' ');
            }
        }
    }
    return 0;
}<file_sep>/farm_tour.cpp
#include<stdio.h>
#include<vector>
using namespace std;
#define INF 1e9
#define MAX_V 1000
#define MAX_E 10000
struct edge{
    int to, cap, cost, rev;
};
vector<edge> G[MAX_V];
int dist[MAX_V];
int prevv[MAX_V];
int preve[MAX_E];
int v, e;

void add_edge(int from, int to, int cap, int cost){
    G[from].push_back((edge) {to, cap, cost, G[to].size()});
    G[to].push_back((edge){from, 0, -cost, G[from].size()-1});
}

int min_cost_flow(int s, int t, int f){
    int res = 0;
    while (f > 0) {
        bool update = true;
        fill(dist, dist+v, INF);
        dist[s] = 0;
        while (update == true) {
            update = false;
            for (int i = 0 ; i < v; i++) {
                for (int j = 0; j < G[i].size(); j++) {
                    edge &ed = G[i][j];
                    if (ed.cap > 0 && dist[i]+ed.cost < dist[ed.to]) {
                        dist[ed.to] = dist[i]+ed.cost;
                        prevv[ed.to] = i;
                        preve[ed.to] = j;
                        update = true;
                    }
                }
            }
        }
        if (dist[t] == INF) {
            return -1;
        }
        int d = f;
        for (int i = t; i != s; i = prevv[i]) {
            d = min(d, G[prevv[i]][preve[i]].cap);
        }
        f -= d;
        res += d*dist[t];
        for (int i = t; i != s; i = prevv[i]) {
            edge &ed = G[prevv[i]][preve[i]];
            ed.cap -= d;
            G[i][ed.rev].cap += d;
        }
    }
    return res;
}

int main(){
    scanf("%d %d", &v, &e);
    int a, b, c;
    for (int i = 0; i < e; i++) {
        scanf("%d %d %d", &a, &b, &c);
        add_edge(a-1, b-1, 1, c);
    }
    printf("%d\n", min_cost_flow(0, v-1, 2));
    return 0;
}



<file_sep>/food_chain.cpp
#include<iostream>
#include<vector>
using namespace std;
#define MAX_K 100000


vector<int> p, rank2, number;


void makeSet(int i){
    p[i] = i;
    rank2[i] = 0;
    number[i] = 1;
}
int find(int i){
    if (i != p[i]) {
        p[i] = find(p[i]);
    }
    return p[i];
}
void link(int x, int y){
    if (x != y) {
        if (rank2[x] < rank2[y]) {
            p[x] = y;
            number[y] += number[x];
        }else{
            p[y] = x;
            number[x] += number[y];
            if (rank2[x] == rank2[y]) {
                rank2[x]++;
            }
        }
    }
}
void unionn(int x, int y){
    link(find(x), find(y));
}

bool same(int x, int y){
    return find(x) == find(y);
}
void init(int size){
    rank2.resize(size, 0);
    p.resize(size, 0);
    number.resize(size, 0);
    for (int i = 0; i < size; i++) {
        makeSet(i);
    }
}

int t[MAX_K], a[MAX_K], b[MAX_K];

int main(){
    int N,K;
    cin >> N >> K;
    
    for (int i = 0; i < K; i++) {
        cin >> t[i] >> a[i] >> b[i];
    }
    init(3*N);
    int ans = 0;
    for (int i = 0; i < K; i++) {
        int x = a[i] -1;
        int y = b[i] -1;
        if (x >=N || y >= N) {
            ans++;
        }else{
            if (t[i] == 1) {
                if (same(x, y+N) || same(x, y+2*N)) {
                    ans++;
                }else{
                    unionn(x,y);
                    unionn(x+N, y+N);
                    unionn(x+2*N, y+2*N);
                }
            }else{
                if (same(x, y) || same(x, y+2*N)) {
                    ans++;
                }else{
                    unionn(x, y+N);
                    unionn(x+N, y+2*N);
                    unionn(x+2*N, y);
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

<file_sep>/bit.cpp
#include<iostream>
#define MAX_N 10000
using namespace std;
int a[MAX_N];
int bit[MAX_N];
int n;

void init(){
    for (int i = 0; i < n+1; i++) {
        bit[i] = 0;
    }
}

int sum(int i){
    int s = 0;
    while (i > 0) {
        s += bit[i];
        i -= i & -i;
    }
    return s;
}
void add(int i, int x){
    while (i <= n) {
        bit[i] += x;
        i += i & -i;
    }
}


int main(){
    int ans = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    init();
    for (int j = 0; j < n; j++) {
        cout << " j = " << j << endl;
        for (int k = 1; k <=n; k++) {
            cout << bit[k] << " " ;
        }
        cout << "sum (a[i])" << sum(a[j]) << endl;
        ans += j-sum(a[j]);
        add(a[j], 1);
        
        cout << ans << endl;
        
    }
    cout << ans << endl;
    return 0;
}
<file_sep>/same_evacuation.cpp
#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
#include<string.h>
using namespace std;
#define MAX_Y 12
#define MAX_X 12
#define MAX_V 1000
char field[MAX_X][MAX_Y+1];
vector<int> dX, dY;
vector<int> pX, pY;
int dist[MAX_X][MAX_Y][MAX_X][MAX_Y];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int X, Y;
int V;
vector<int> G[MAX_V];
int match[MAX_V];
bool used[MAX_V];

void add_edge(int i, int u){
    G[i].push_back(u);
    G[u].push_back(i);
}

bool dfs(int i){
    used[i] = true;
    for (int j = 0; j < G[i].size(); j++) {
        int u = G[i][j], w = match[u];
        if (w < 0 || (!used[w] && dfs(w))) {
            match[i] = u;
            match[u] = i;
            return true;
        }
    }
    return false;
}



int bipartite_matching(){
    int res = 0;
    memset(match, -1, sizeof(match));
    for (int i = 0; i < V; i++) {
        if (match[i] < 0) {
            memset(used, 0, sizeof(used));
            if (dfs(i)) {
                res++;
            }
        }
    }
    return res;
}
bool C(int t){
    int d = dX.size(), p = pX.size();
    V = t*d+p;
    for (int i = 0; i < V; i++) {
        G[i].clear();
    }
    for (int i = 0; i < d; i++) {
        for (int j = 0; j < p; j++) {
            if (dist[dX[i]][dY[i]][pX[j]][pY[j]] >= 0) {
                for (int k = dist[dX[i]][dY[i]][pX[j]][pY[j]]; k <= t; k++) {
                    add_edge((k-1)*d+i, t*d+j);
                    cout << "left " << (k-1)*d+i << " right " << t*d+j << endl;
                    
                }
            }
        }
    }
    cout << "-------" << endl;
    return bipartite_matching() == p;
}




void bfs(int x, int y, int d[MAX_X][MAX_Y]){
    queue<int> qx, qy;
    d[x][y] = 0;
    qx.push(x);
    qy.push(y);
    int depth = 0;
    int next = 0;
    while(!qx.empty()){
        int nx = qx.front();
        qx.pop();
        int ny = qy.front();
        qy.pop();
        for(int i = 0; i < 4; i++){
            int nextx = nx+dx[i], nexty = ny+dy[i];
            if (nextx >= 0 && nextx < X && nexty >= 0 && nexty < Y && field[nextx][nexty] == '.' && d[nextx][nexty] < 0){
                d[nextx][nexty] = d[nx][ny]+1;
                qx.push(nextx);
                qy.push(nexty);
            }
        }
    }
}


void solve(){
    int n = X*Y;
    dX.clear();
    dY.clear();
    pX.clear();
    pY.clear();
    memset(dist, -1, sizeof(dist));
    for (int x = 0; x < X; x++) {
        for (int y = 0; y < Y; y++) {
            if (field[x][y] == 'D') {
                dX.push_back(x);
                dY.push_back(y);
                bfs(x, y, dist[x][y]);
            }else if(field[x][y] == '.'){
                pX.push_back(x);
                pY.push_back(y);
            }
        }
    }
    int lb = -1, ub = n+1;
    while (ub-lb > 1) {
        int mid = (lb+ub)/2;
        cout << "----------"<<endl;
        cout << "mid " << mid << endl;
        if(C(mid))ub = mid;
        else lb = mid;
    }
    if(ub > n){
        cout << "impossible" << endl;
    }else{
        cout << ub << endl;
    }
}

int main(){
    int t;
    scanf("%d", &t);
    for (int i = 0; i < t; i++) {
        scanf("%d%d", &X, &Y);
        for (int j = 0; j < X; j++) {
            for (int k = 0; k < Y; k++) {
                cin >> field[j][k];
            }
        }
        solve();
    }
    return 0;
}
<file_sep>/evacuation.cpp
#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
#include<string.h>
using namespace std;
#define MAX_Y 12
#define MAX_X 12
#define MAX_V 244
char dat[MAX_Y][MAX_X];
vector<int> dX, dY;
vector<int> pX, pY;
int d[MAX_Y][MAX_X][MAX_Y][MAX_X];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int X, Y;
int V;
vector<int> G[MAX_V];
int match[MAX_V];
bool used[MAX_V];

void add_edge(int i, int u){
    G[i].push_back(u);
    G[u].push_back(i);
}

bool dfs(int i){
    used[i] = true;
    for (int j = 0; j < G[i].size(); j++) {
        int u = G[i][j], w = match[u];
        if (w < 0 || (!used[w] && dfs(w))) {
            match[i] = u;
            match[u] = i;
            return true;
        }
    }
    return false;
}



int bipartite_matching(){
    int res = 0;
    for (int i = 0; i < V; i++) {
        if (match[i] < 0) {
            memset(used, 0, sizeof(used));
            if (dfs(i)) {
                res++;
            }
        }
    }
    return res;
}
bool C(int t){
    int door = dX.size(), people = pX.size();
    cout << door << " " << people << endl;
    for (int i = 0; i < t*door+people; i++) {
        G[i].clear();
    }
    for (int i = 0; i < door; i++) {
        for (int j = 0; j < people; j++) {
            if (d[dY[i]][dX[i]][pY[j]][pX[j]] >= 0) {
                for (int k = d[dY[i]][dX[i]][pY[j]][pX[j]]; k <= t; k++) {
                    add_edge((k-1)*door+i, t*door+j);
                    if (t == 12) {
                        cout << "left " << (k-1)*door+i << " right " << t*door+j<< endl;
                    }
                }
            }
        }
    }
    memset(match, -1, sizeof(match));
    return bipartite_matching() == people;
}




void bfs(int x, int y){
    queue<int> qx, qy;
    qx.push(x);
    qy.push(y);
    int depth = 0;
    int current = 1;
    int next = 0;
    while(!qx.empty()){
        int nx = qx.front();
        qx.pop();
        int ny = qy.front();
        qy.pop();
        current--;
        if(dat[ny][nx] == '.'){
            d[y][x][ny][nx] = depth;
            //cout << "hello" << endl;
            //cout << x << " " << y << " " << nx << " " << ny << endl;
        }
        for(int i = 0; i < 4; i++){
            int nextx = nx+dx[i], nexty = ny+dy[i];
            if (nextx >= 0 && nextx < X && nexty >= 0 && nexty < Y ){
                if(dat[nexty][nextx] == '.' && d[y][x][nexty][nextx] < 0){
                    qx.push(nextx);
                    qy.push(nexty);
                    next++;
                }
            }
        }
        if(current == 0){
            current = next;
            next = 0;
            depth++;
        }
    }
}


int main(){
    int t;
    scanf("%d", &t);
    for (int i = 0; i < t; i++) {
        scanf("%d%d", &Y, &X);
        memset(d, -1, sizeof(d));
        //cout << X << " " << Y;
        for (int j = 0; j < Y; j++) {
            for (int k = 0; k < X; k++) {
                cin >> dat[j][k];
            }
            //cout << endl;
            for (int k = 0; k < X; k++) {
                //cout << dat[j][k];
            }
        }
        //cout << "out "<< endl;
        for (int j = 0; j < Y; j++) {
            for (int k = 0; k < X; k++) {
                if (dat[j][k] == 'D') {
                    dX.push_back(k);
                    dY.push_back(j);
                    bfs(k, j);
                }else if(dat[j][k] == '.'){
                    pX.push_back(k);
                    pY.push_back(j);
                }
            }
        }
        int n = X*Y;
        int lb = -1;
        int ub = n+1;
        while (ub - lb > 1) {
            int mid = (lb+ub)/2;
            cout << lb <<" " << ub << " " << mid << endl;
            if(C(mid)) ub = mid;
            else lb = mid;
        }
        if (ub > n) {
            cout << "Impossible"<< endl;
        }else{
            cout << ub<< endl;
        }
        for (int j = 0; j < Y; j++) {
            for (int k = 0; k < X; k++) {
                if(dat[j][k] == 'D'){
                    cout << "door " << j << " " << k << endl;
                    for (int l = 0; l < Y; l++) {
                        for (int m = 0; m < X; m++) {
                            if(dat[l][m] == '.'){
                                cout << d[j][k][l][m];
                            }else{
                                cout << dat[l][m];
                            }
                        }
                        cout << endl;
                    }
                }
                cout << endl;
            }
        }
        
    }
    return 0;
}
<file_sep>/cow_face.cpp
#include<iostream>
#include<string.h>
using namespace std;
#define N 5000
bool f[N];
int dir[N];
int n;

int cal(int k){
    memset(f, 0, sizeof(f));
    int sum = 0;
    int ans = 0;
    for (int i = 0; i <= n-k; i++) {
        if ((dir[i]+sum)%2==1) {
            ans++;
            f[i] = 1;
        }
        sum += f[i];
        if (i-k+1 >= 0) {
            sum -= f[i-k+1];
        }
    }
    for (int i = n-k+1; i < n; i++) {
        if ((dir[i]+sum)%2==1) {
            return -1;
        }
        if (i-k+1 >= 0) {
            sum -= f[i-k+1];
        }
    }
    return ans;
}




int main(){
    cin >> n;
    char c;
    for (int i = 0; i < n; i++) {
        cin >> c;
        if (c == 'B') {
            dir[i] = 1;
        }else{
            dir[i] = 0;
        }
    }
    int res = n;
    int res2 = 1;
    for (int i = 1; i <= n; i++) {
        int tmp = cal(i);
        if (tmp >= 0 &&tmp < res) {
            res = tmp;
            res2 = i;
        }
    }
    cout << res2 << " " << res << endl;
    return 0;
}<file_sep>/asteroids.cpp
#include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;
#define MAX_N 500

int n, k;

vector<int> G[MAX_N*2];
int match[MAX_N*2];
bool used[MAX_N*2];

void add_edge(int i, int u){
    G[i].push_back(u);
    G[u].push_back(i);
}

bool dfs(int i){
    used[i] = true;
    for (int j = 0; j < G[i].size(); j++) {
        int u = G[i][j], w = match[u];
        if (w < 0 || (!used[w] && dfs(w))) {
            match[i] = u;
            match[u] = i;
            return true;
        }
    }
    return false;
}

int bipartite_matching(){
    int res = 0;
    for (int i = 0; i < n*2; i++) {
        if (match[i] < 0) {
            memset(used, 0, sizeof(used));
            if (dfs(i)) {
                res++;
            }
        }
    }
    return res;
}

int main (){
    while(scanf("%d%d", &n, &k) != EOF) {
        int r, c;
        for (int i = 0; i < k; i++) {
            scanf("%d%d", &r, &c);
            add_edge(r-1, n+c-1);
        }
        memset(match, -1, sizeof(match));
        printf("%d\n", bipartite_matching());
    }
    return 0;
}<file_sep>/dining.cpp
#include<stdio.h>
#include<vector>
#include<string.h>
using namespace std;
#define MAX_N 100
#define MAX_F 100
#define MAX_D 100
#define INF 1e9
#define MAX_V 405
#define MAX_E 100000

struct edge{
    int to;
    int cap;
    int rev;
};

vector<edge> G[MAX_N*2+MAX_F+MAX_D+2];
bool used[MAX_V];

void add_edge(int from, int to, int cap){
    G[from].push_back((edge){to, cap, G[to].size()});
    G[to].push_back((edge){from, 0, G[from].size()-1});
}

int dfs(int v, int t, int f){
    if (v == t) {
        return f;
    }
    used[v] = true;
    for (int i = 0; i < G[v].size(); i++) {
        edge &e = G[v][i];
        if (!used[e.to] && e.cap > 0) {
            int d = dfs(e.to, t, min(f, e.cap));
            if (d > 0) {
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

int max_flow(int s, int t){
    int flow = 0;
    for (; ; ) {
        memset(used, 0, sizeof(used));
        int f = dfs(s,t, INF);
        if (f == 0) {
            return flow;
        }
        flow+=f;
    }
}

int main(){
    int n, f, d;
    scanf("%d %d %d", &n, &f, &d);
    for (int i = 1; i <= f; i++) {
        add_edge(0, i, 1);
    }
    for (int i = f+n*2+1; i <= f+n*2+d; i++) {
        add_edge(i, f+n*2+d+1, 1);
    }
    for (int i = f+1; i <=f+n; i++) {
        add_edge(i, i+n, 1);
    }
    int fi, di;
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &fi, &di);
        int a;
        for (int j = 0; j < fi; j++) {
            scanf("%d", &a);
            add_edge(a, f+i, 1);
        }
        
        for (int j = 0; j < di; j++) {
            scanf("%d", &a);
            add_edge(f+n+i, f+n*2+a, 1);
        }
    }
    int ans = max_flow(0, f+n*2+d+1);
    printf("%d\n", ans);
    return 0;
}<file_sep>/add_integers_segment.cpp
#include<iostream>
#include<algorithm>
#define SIZE 200000
using namespace std;
int n, q;
int data[SIZE];
int datb[SIZE];


void add(int a, int b, int x, int k, int l, int r){
    
    if (b >= r && a <= l) {
        data[k] += x;
        return;
    }else if(b > l && a < r){
        datb[k]+= (min(b,r)-max(a,l))*x;
        int m = (l+r)/2;
        add(a, b, x, 2*k+1, l, m);
        add(a, b, x, 2*k+2, m, r);
    }
}

int sum(int a, int b, int k, int l, int r){
    if (a >= r || b <= l) {
        return 0;
    }
    if (b >= r && a <= l) {
        return data[k]*(r-l)+datb[k];
    }
    long long res = (min(b,r)-max(a,l))*data[k];
    int m = (l+r)/2;
    res += sum(a, b, 2*k+1, l, m);
    res += sum(a, b, 2*k+2, m, r);
    return res;
}



int main(){
    cin >> n >> q;
    int num;
    for (int i = 0; i < n; i++) {
        cin >> num;
        add(i, i+1, num, 0, 0, n);
    }
    cout << endl;
    for (int i = 0; i < 3*n+1; i++) {
        cout << datb[i] << " ";
    }
    cout << endl;
    for (int i = 0; i < 3*n+1; i++) {
        cout << data[i] << " ";
    }
    cout << endl;
    char c;
    int x, y, z;
    for (int i = 0; i < q; i++) {
        cin >> c;
        if (c == 'C') {
            cin >> x >> y >> z;
            add(x-1, y, z, 0, 0, n);
        }else{
            cin >> x >> y;
            cout << sum(x-1, y, 0, 0, n)<<endl;
        }
    }
    return 0;
}<file_sep>/expedition.cpp
#include<iostream>
#include<queue>
#include<utility>
#include<algorithm>
#include<vector>
using namespace std;
#define MAX_N 10000
//int a[MAX_N+1], b[MAX_N+1];
vector<pair<int,int> > v;

bool pairCompare(const pair<int,int>& one, const pair<int,int>& two){
    return one.first < two.first;
}


int main(){
    int N, L, P;
    cin >> N;
    int a, b;
    for (int i = 0; i < N ; i++) {
        cin >> a >> b;
        v.push_back(make_pair(a,b));
    }
    cin >> L >> P;
    for (int i = 0; i < N; i++) {
        v[i].first = L-v[i].first;
    }
    v.push_back(make_pair(L,0));
    sort(v.begin(), v.end(), pairCompare);
    priority_queue<int> q;
    bool f = true;
    int ans = 0;
    for ( int i = 0; i <= N; i++) {
        while (P < v[i].first && !q.empty()) {
            P += q.top();
            q.pop();
            ans++;
        }
        if (P < v[i].first) {
            f = false;
            break;
        }else{
            q.push(v[i].second);
        }
    }
    if (f) {
        cout << ans << endl;
    }else{
        cout << -1 << endl;
    }
    return 0;
}<file_sep>/aggressive_cows.cpp
#include<stdio.h>
#include<algorithm>
using namespace std;
#define N 100000
int x[N];
int n;

bool ok(int m, int c){
    int prev = x[0];
    c--;
    for (int i = 1; i < n; i++) {
        if (x[i] - prev >= m) {
            prev = x[i];
            c--;
            if (c == 0) {
                return true;
            }
        }
    }
    return false;
}

int main(){
    int c;
    scanf("%d%d",&n, &c);
    for (int i = 0; i < n; i++) {
        scanf("%d", &x[i]);
    }
    sort(x, x+n);
    int lb = 1;
    int ub = (x[n-1]-x[0])/(c-1);
    int ans;
    while (lb <= ub) {
        int mid = (lb+ub)/2;
        if(ok(mid, c)){
            ans = mid;
            lb = mid+1;
        }else{
            ub = mid-1;
        }
    }
    printf("%d\n", ans);
    return 0;
}<file_sep>/layout.cpp
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<vector>
using namespace std;
#define N 1000
#define INF 1000001
struct edge {
    int from, cost;
};
vector<edge> g[N];
int d[N];

int main(){
    int n, ml, md;
    cin >> n >> ml >> md;
    int a, b, l;
    for (int i = 0; i < ml; i++) {
        scanf("%d%d%d", &a, &b, &l);
        a--;
        b--;
        edge e;
        e.from = a;
        e.cost = l;
        g[b].push_back(e);
    }
    for (int i = 0; i < md; i++) {
        scanf("%d%d%d", &a, &b, &l);
        a--;
        b--;
        edge e;
        e.from = b;
        e.cost = -l;
        g[a].push_back(e);
    }
    for (int i = 0; i < n-1; i++) {
        edge e;
        e.from = i+1;
        e.cost = 0;
        g[i].push_back(e);
    }
    for (int i = 0; i < n; i++) {
        d[i] = INF;
    }
    d[0] = 0;
    for (int k = 0; k < n; k++) {
        bool update = false;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < g[i].size(); j++) {
                edge e = g[i][j];
                if (d[e.from]+e.cost < d[i]) {
                    d[i] = d[e.from]+e.cost;
                }
            }
        }
        
    }
    if (d[n-1] == INF) {
        cout << -2 << endl;
    }else if(d[0] < 0){
        cout << -1 << endl;
    }else{
        cout << d[n-1] << endl;
    }
    return 0;
}<file_sep>/traveling_stagecoach.cpp
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string.h>
using namespace std;
#define MAX_N 8
#define MAX_M 30
#define INF 1e9 + 7
int d[MAX_M][MAX_M];
double dp[1<<MAX_N][MAX_M];
int t[MAX_N];

int main(){
    int n,m, a, b, p;
    while(scanf("%d%d%d%d%d", &n, &m, &p, &a, &b) != EOF && n > 0){
        for (int i = 0; i < n; i++) {
            scanf("%d", &t[i]);
        }
        memset(d, -1, sizeof(d));
        int x, y, z;
        for (int i = 0; i < p; i++) {
            scanf("%d%d%d", &x, &y, &z);
            x--;
            y--;
            d[x][y] = z;
            d[y][x] = z;
        }
        for (int i = 0; i < 1 <<n; i++) {
            fill(dp[i], dp[i]+m, INF);
        }
        dp[(1<<n)-1][a-1] = 0.0;
        
        double res = INF;
        for (int S = (1<<n)-1; S >= 0; S--) {
            res = min(res, dp[S][b-1]);
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (S>>j&1) {
                        for (int u = 0; u < m; u++) {
                            if(d[i][u] > -1){
                                dp[S & ~(1<<j)][u] = min(dp[S & ~(1<<j)][u], dp[S][i]+(double)d[i][u]/(double)t[j]);
                            }
                        }
                    }
                }
            }
        }
        if (res == INF) {
            printf("Impossible\n");
        }else{
            printf("%.3f\n", res);
        }
    }
    return 0;
}<file_sep>/jack_straws.cpp
#include<stdio.h>
using namespace std;
#define MAX_N 13
int n;
vector<int> G[MAX_N];

double add(double a, double b){
    if (abs(a+b) < EPS * (abs(a) + abs(b))) {
        return 0;
    }
    return a + b;
}


struct P{
    double x, y;
    P() {}
    P(double x, double y) : x(x), y(y){
    }
    P operator + (P p){
        return P(add(x, p.x), add(y, p.y));
    }
    P operator - (P p){
        return P(add(x, -p.x), add(y, -p.y));
    }
    P operator * (double d){
        return P(x*d, y*d);
    }
    double dot(P p){
        return add(x*p.x, y*p.y);
    }
    double det(P p){
        return add(x*p.y, -y*p.x);
    }
};


bool on_seg(P p1, P p2, P q1, P q2){
    
}

bool isCrossDirectly(P p1, P p2, P q1, P q2){
    
}

int main(){
    scanf("%d", &n);
    int x1, y1, x2, y2;
    for (int i = 0; i < n; i++) {
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
    }
    int a = 1, b = 1;
    while (a != 0 && b != 0) {
        scanf("%d %d", &a, &b);
        
    }
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            
            isCrossDirectly(
        }
    }
	return 0;
}
<file_sep>/cable_master.cpp
#include<math.h>
#include<algorithm>
#include<stdio.h>
using namespace std;
#define EPS 0.0001
int main(){
    int n, k;
    scanf("%d%d", &n, &k);
    double l[n];
    double sum = 0.0;
    for (int i = 0; i < n; i++) {
        scanf("%lf",&l[i]);
        sum += l[i];
    }
    double s = 0.0;
    double t = sum/k;
    double m;
    for (int j = 0; j < 100; j++) {
        m = (t+s)/2;
        int num = 0;
        for (int i = 0; i < n; i++) {
            num += (int)(l[i]/m);
        }
        if(num < k){
            t = m;
        }else{
            s = m;
        }
    }
    printf("%.2f\n", floor(m*100)/100);
    return 0;
}<file_sep>/windy.cpp
#include<stdio.h>
#include<vector>
using namespace std;
#define N 50
#define M 50
#define MAX_V 2602
#define INF 1e9
#define MAX_E 125100

struct edge{
    int to, cap, cost, rev;
};
vector<edge> G[MAX_V];
int dist[MAX_V];
int prevv[MAX_V];
int preve[MAX_E];
int v;

void add_edge(int from, int to, int cap, int cost){
    G[from].push_back((edge) {to, cap, cost, G[to].size()});
    G[to].push_back((edge){from, 0, -cost, G[from].size()-1});
}

int min_cost_flow(int s, int t, int f){
    int res = 0;
    while (f > 0) {
        bool update = true;
        fill(dist, dist+v, INF);
        dist[s] = 0;
        while (update == true) {
            update = false;
            for (int i = 0 ; i < v; i++) {
                for (int j = 0; j < G[i].size(); j++) {
                    edge &ed = G[i][j];
                    if (ed.cap > 0 && dist[i]+ed.cost < dist[ed.to]) {
                        dist[ed.to] = dist[i]+ed.cost;
                        prevv[ed.to] = i;
                        preve[ed.to] = j;
                        update = true;
                    }
                }
            }
        }
        if (dist[t] == INF) {
            return -1;
        }
        int d = f;
        for (int i = t; i != s; i = prevv[i]) {
            d = min(d, G[prevv[i]][preve[i]].cap);
        }
        f -= d;
        res += d*dist[t];
        for (int i = t; i != s; i = prevv[i]) {
            edge &ed = G[prevv[i]][preve[i]];
            ed.cap -= d;
            G[i][ed.rev].cap += d;
        }
    }
    return res;
}

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    v = 2+n+m+n*m;
    int s = n+m*n+m;
    int t = s+1;
    int a;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &a);
            for (int k = 0; k < n; k++) {
                add_edge(i, n+j*n+k, 1, a*(k+1));
            }
        }
    }
    
    for (int i = 0; i < n; i++) {
        add_edge(s, i, 1, 0);
    }
    for (int i = n; i < v-2; i++) {
        add_edge(i, t, 1, 0);
    }
    printf("%.2lf\n", (double)min_cost_flow(s, t, n)/n);
    return 0;
}<file_sep>/evacuation_sample.cpp
#include<cstdio>
#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#define MAX_X 15
#define MAX_Y 15
#define MAX_V 15*15*100
using namespace std;


struct P { int x, y; };

int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

int X, Y;
char field[MAX_X][MAX_Y];

int dist[MAX_X][MAX_Y][MAX_X][MAX_Y];
vector<P> ds, ps;

vector<int> G[MAX_V];
int match[MAX_V];
bool used[MAX_V];

void add_edge(int u, int v){
  G[u].push_back(v);
  G[v].push_back(u);
}

bool dfs(int v){
  used[v] = true;
  for(int i = 0; i < G[v].size(); i++){
    int u = G[v][i];
    int u_pair = match[u];
    if(u_pair < 0 || (!used[u_pair] && dfs(u_pair))){
      match[v] = u;
      match[u] = v;
      return true;
    }
  }
  return false;
}

void bfs(P door, int d[MAX_X][MAX_Y]){
  queue<P> q;
  d[door.x][door.y] = 0;
  q.push(door);
  while(!q.empty()){
    P p = q.front(); q.pop();
    for(int i = 0; i < 4; i++){
      int nx = p.x + dx[i], ny = p.y + dy[i];
      if(field[nx][ny] == '.' && d[nx][ny] < 0){
        d[nx][ny] = d[p.x][p.y] + 1;
        q.push((P){nx, ny});
      }
    }
  }
}

void solve(){
  int max_t = X * Y;
  ds.clear(); ps.clear();
  memset(dist, -1, sizeof(dist));
  for(int i = 0; i < MAX_V; i++){
    G[i].clear();
  }

  for(int x = 0; x < MAX_X; x++){
    for(int y = 0; y < MAX_Y; y++){
      if(field[x][y] == 'D'){
        ds.push_back((P){x, y});
        bfs((P){x, y}, dist[x][y]);
      }else if(field[x][y] == '.'){
        ps.push_back((P){x, y});
      }
    }
  }

  for(int i = 0; i < ds.size(); i++){
    for(int j = 0; j < ps.size(); j++){
      P d = ds[i], p = ps[j];
      if(dist[d.x][d.y][p.x][p.y] >= 0){
        for(int t = dist[d.x][d.y][p.x][p.y]; t <= max_t; t++){
          add_edge((t - 1) * ds.size() + i, max_t * ds.size() + j);
            cout << "max_t " << max_t << endl;
            if (max_t == 12) {
                cout << "left " << (t-1)*ds.size()+i << " right " << max_t * ds.size() + j<< endl;
            }
        }
      }
    }
  }

  if(ps.size() == 0){
    printf("0\n");
    return;
  }

  int num = 0;
  memset(match, -1, sizeof(match));
  for(int v = 0; v < max_t * ds.size(); v++){
    memset(used, 0, sizeof(used));
    if(dfs(v)){
      if(++num == ps.size()){
        printf("%lu\n", (v / ds.size() + 1));
        return;
      }
    }
  }
  printf("impossible\n");
}

int main(){
  int C;
  scanf("%d", &C);

  while(C--){
    scanf("%d %d", &X, &Y);
    memset(field, 'X', sizeof(field));
    for(int i = 1; i <= X; i++){
      scanf("%s", &field[i][1]);
    }
    solve();
  }
}
<file_sep>/domino_backtrack.cpp
#include<iostream>
using namespace std;
#define MAX_N 1000
#define M 1000000000
char a[MAX_N][MAX_N];
int remain, n;
int ans = 0;
int x[2] = {1, 0};
int y[2] = {0, 1};

//void print(){
//    cout << "-----------"<< endl;
//    for (int i = 0; i < n; i++) {
//        for (int j = 0; j < n; j++) {
//            cout << a[i][j];
//        }
//        cout << " | ";
//        for (int j = 0; j < n; j++) {
//            cout << used[i][j];
//        }
//        cout << endl;
//    }
//    cout << "-----------"<< endl;
//}

//void dfs(int i, int j){
//    used[i][j] = true;
//    for (int k = 0; k < 2; k++) {
//        int ni = i+x[k], nj = j+y[k];
//        if (ni >= 0 && ni < n && nj >= 0 && nj < n && a[ni][nj] == '.') {
//            a[i][j] = 'x';
//            a[ni][nj] = 'x';
//            print();
//            remain -= 2;
//            if (remain == 0) {
//                ans++;
//            }else{
//                for (int l = 0; l < n; l++) {
//                    for (int m = 0; m < n; m++) {
//                        if (a[l][m] == '.' && !used[l][m]) {
//                            dfs(l, m);
//                        }
//                    }
//                }
//            }
//            a[i][j] = '.';
//            a[ni][nj] = '.';
//            remain += 2;
//            used[i][j] = false;
//
//        }
//    }
//}


int rec(int i, int j, bool used[MAX_N][MAX_N]){
    cout << i << endl;
    if (j == n) {
        return rec(i+1, 0, used);
    }
    if (i == n) {
        cout << "here" << endl;
        return 1;
    }
    if (used[i][j] || a[i][j]=='x') {
        return rec(i, j+1, used);
    }
    int res = 0;
    used[i][j] = true;
    if (j+1 < n && !used[i][j+1] && a[i][j+1] == '.') {
        used[i][j+1] = true;
        cout << "here1" << endl;

        res += rec(i, j+1, used);
        used[i][j+1] = false;
    }
    if (i+1 < n && !used[i+1][j] && a[i+1][j] == '.') {
        used[i+1][j] = true;
        cout << "here2" << endl;

        res += rec(i, j+1, used);
        used[i+1][j] = false;
    }
    used[i][j] = false;
    return res % M;
}


int main(){
    cin >> n;
    int si, sj;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << a[i][j];
        }
        cout << endl;
    }
    //dfs(si, sj);
    bool used[MAX_N][MAX_N];
    memset(used, 0, sizeof(used));
    cout << rec(0, 0, used) << endl;
    return 0;
}<file_sep>/intervals.cpp
#include<iostream>
#include<utility>
#include<vector>
using namespace std;
#define MAX_V 200
#define INF 1e9
#define MAX_E 1000
int N, k, v;
struct edge{
    int to, cap, cost, rev;
};
vector<edge> G[MAX_V];
int dist[MAX_V];
int prevv[MAX_V];
int preve[MAX_E];
void add_edge(int from, int to, int cap, int cost){
    G[from].push_back((edge) {to, cap, cost, G[to].size()});
    G[to].push_back((edge){from, 0, -cost, G[from].size()-1});
}

int min_cost_flow(int s, int t, int f){
    int res = 0;
    while (f > 0) {
        bool update = true;
        fill(dist, dist+v, INF);
        dist[s] = 0;
        while (update == true) {
            update = false;
            for (int i = 0 ; i < v; i++) {
                for (int j = 0; j < G[i].size(); j++) {
                    edge &ed = G[i][j];
                    if (ed.cap > 0 && dist[i]+ed.cost < dist[ed.to]) {
                        dist[ed.to] = dist[i]+ed.cost;
                        prevv[ed.to] = i;
                        preve[ed.to] = j;
                        update = true;
                    }
                }
            }
        }
        if (dist[t] == INF) {
            return -1;
        }
        int d = f;
        for (int i = t; i != s; i = prevv[i]) {
            d = min(d, G[prevv[i]][preve[i]].cap);
        }
        f -= d;
        res += d*dist[t];
        for (int i = t; i != s; i = prevv[i]) {
            edge &ed = G[prevv[i]][preve[i]];
            ed.cap -= d;
            G[i][ed.rev].cap += d;
        }
    }
    return res;
}

int main(){
    scanf("%d %d", &N, &k);
    int a[MAX_V], b[MAX_V], w[MAX_V];
    vector<int> x;
    int s, t;
    
    
    for (int i = 0; i < N; i++) {
        scanf("%d %d %d", &a[i], &b[i], &w[i]);
        x.push_back(a[i]);
        x.push_back(b[i]);
    }
    sort(x.begin(), x.end());
    x.erase(unique(x.begin(), x.end()), x.end());
    int m = x.size();
    s = m;
    t = s+1;
    v = t + 1;
    
    for(int i = 0; i < v; i++){
        G[i].clear();
    }
    int res = 0;
    add_edge(s, 0, k, 0);
    add_edge(m-1, t, k, 0);
    for (int i = 0; i < m-1; i++) {
        add_edge(i, i+1, INF, 0);
    }

    for (int i = 0; i < N; i++) {
        int u = find(x.begin(), x.end(), a[i]) - x.begin();
        int y = find(x.begin(), x.end(), b[i]) - x.begin();
        add_edge(y, u, 1, w[i]);
        add_edge(s, y, 1, 0);
        add_edge(u, t, 1, 0);
        res -= w[i];
    }
    
    res += min_cost_flow(s, t, k+N);
    printf("%d\n", -res);
    return 0;
}<file_sep>/physics.cpp
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<algorithm>
#define N 100
#define g 10.0
using namespace std;
int n, h, r, t;
double y[N];

double cal(int t){
    if (t < 0) {
        return h;
    }
    double T = sqrt(2*h/g);
    int k = (int)(t/T);
    if (k % 2 == 0) {
        double d = t-k*T;
        return h-g*d*d/2;
    }else{
        double d = (k+1)*T-t;
        return h-g*d*d/2;
    }
}

int main(){
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        cin >> n >> h >> r >> t;
        for (int j = 0; j < n; j++) {
            y[j] = cal(t-j);
        }
        sort(y, y+n);
        for (int j = 0; j < n; j++) {
            printf("%.2f%c", y[j]+2*r*j/100.0, j+1 == n ? '\n' : ' ');
        }
        
    }
    return 0;
}<file_sep>/temp.cpp
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
using namespace std;
#define REP(i, j) for(int i = 0; i < (int)(j); ++i)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define P pair<int, int>
#define SORT(v) sort((v).begin(), (v).end())
#define REVERSE(v) reverse((v).begin(), (v).end())
//#define int long long
const int MAX_N = 1e5 + 10;
const int MAX_ST = (1 << 18) - 1;

int N, M, A[MAX_N], sorted_A[MAX_N];
vector<int> seg[MAX_ST];

void init(int k, int l, int r){
  if(r - l <= 1) seg[k].push_back(A[l]);
  else{
    int chl = k * 2 + 1, chr = k * 2 + 2;
    init(chl, l, (l + r) / 2);
    init(chr, (l + r) / 2, r);
    seg[k].resize(r - l);
    merge(seg[chl].begin(), seg[chl].end(), seg[chr].begin(), seg[chr].end(), seg[k].begin());
  }
}

int cnt(int a, int b, int x, int k, int l, int r){
  if(r <= a || l >= b) return 0;
  else if(l >= a && r <= b) return upper_bound(seg[k].begin(), seg[k].end(), x) - seg[k].begin();
  return cnt(a, b, x, k * 2 + 1, l, (l + r) / 2) + cnt(a, b, x, k * 2 + 2, (l + r) / 2, r);
}

int main() {
  scanf("%d %d", &N, &M);
  REP(i, N){
    scanf("%d", &A[i]);
    sorted_A[i] = A[i];
  }
  sort(sorted_A, sorted_A + N);
  init(0, 0, N);
  REP(z, M){
    int l, r, k; scanf("%d %d %d", &l, &r, &k);
    --l;
    int hi = N - 1, lo = -1;
    while(hi - lo > 1){
      int m = (hi + lo) / 2, x = sorted_A[m];
      int c = cnt(l, r, x, 0, 0, N);
      //debug
      cout <<lo <<", " <<m <<", " <<hi <<" | " <<x <<", " <<c <<endl;
      if(c >= k) hi = m;
      else lo = m;
    }
    printf("%d\n", sorted_A[hi]);
  }
  return 0;
}
<file_sep>/k-th_number_segment.cpp
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

const int ST_SIZE = (1 << 18) -1;
#define MAX_N 100000
vector<int> dat[ST_SIZE];
int a[MAX_N];
int num[MAX_N];

void init(int k, int l, int r){
    if (r - l <= 1) {
        dat[k].push_back(a[l]);
    }else{
        int lch = k*2+1, rch = k*2+2, m = (l+r)/2;
        init(lch, l, m);
        init(rch, m, r);
        dat[k].resize(r-l);
        merge(dat[lch].begin(), dat[lch].end(), dat[rch].begin(), dat[rch].end(), dat[k].begin());
    }
}
int query(int i, int j, int x, int k, int l, int r){
    if (j <= l || i >= r) {
        return 0;
    }else if(i <= l && j >= r){
        return upper_bound(dat[k].begin(),dat[k].end(),x)-dat[k].begin();
    }else{
        return query(i, j, x, k*2+1, l, (l+r)/2) + query(i, j, x, k*2+2, (l+r)/2, r);
    }
}

int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        num[i] = a[i];
    }
    sort(num, num+n);
    init(0, 0, n);
    int i, j, k;
    for (int t = 0; t < m; t++) {
        scanf("%d%d%d", &i, &j, &k);
        int lb = -1;
        int ub = n-1;
        i--;
        while(ub - lb > 1){
            int md = (ub+lb)/2;
            int c = query(i, j, num[md], 0, 0, n);
            if (c >= k) {
                ub = md;
            }else{
                lb = md;
            }
        }
        printf("%d\n", num[ub]);
    }
    return 0;
}
<file_sep>/fliptile.cpp
#include<iostream>
#include<stdio.h>
#include<string.h>
#define M 15
#define N 15
using namespace std;
int m, n;

int x[5] = {-1, 0,0, 0 ,1 };
int y[5] = {0,-1, 0, 1, 0 };
int ans[M][N];
int flip[M][N];
int tile[M][N];
int res = -1;
int res1 = 0;
int opt[M][N];

bool whilteOrNot(int i, int j){
    if ((tile[i][j] + flip[i][j])%2 == 0) {
        return true;
    }else{
        return false;
    }
}

int cal(){
    int a = 0;
    for (int i = 1; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (whilteOrNot(i-1, j) == false) {
                //if i-1, j is black
                ans[i][j] = 1;
                a++;
                for (int k = 0; k < 5; k++) {
                    int x2 = i+x[k];
                    int y2 = j+y[k];
                    if (x2 >= 0 && x2 < m && y2 >= 0 && y2 < n) {
                        flip[x2][y2]++;
                    }
                }
            }
        }
    }
    return a;
}

bool check(){
    for (int i = 0; i < n; i++) {
        if ((tile[m-1][i]+flip[m-1][i])%2!=0) {
            return false;
        }
    }
    return true;
}



int main(){
    cin >> m >> n;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &tile[i][j]);
        }
    }
    for (int i = 0; i < 1 << n; i++) {
        memset(flip, 0, sizeof(flip));
        res1 = 0;
        for (int j = 0; j < n; j++) {
            int a = n-1-j;
            int b = i >> j & 1;
            ans[0][a] = b;
            if (b == 1) {
                res1++;
                for (int k = 0; k < 5; k++) {
                    int x2 = 0+x[k];
                    int y2 = a+y[k];
                    if (x2 >= 0 && x2 < m && y2 >= 0 && y2 < n) {
                        flip[x2][y2]++;
                    }
                }
            }
        }
        res1 += cal();
        if (check()==true && (res1 < res||res < 0)) {
            res = res1;
            for (int j = 0; j < m; j++) {
                for (int k = 0; k < n; k++) {
                    opt[j][k] = ans[j][k];
                    ans[j][k] = 0;
                }
            }
        }
    }
    if (res < 0) {
        cout << "IMPOSSIBLE" << endl;
    }else{
        for (int j = 0; j < m; j++) {
            for (int k = 0; k < n; k++) {
                printf("%d%c", opt[j][k], k+1==n ? '\n' : ' ');
            }
        }
    }
    return 0;
}<file_sep>/jessica.cpp
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;

int main(){
    int p;
    cin >> p;
    int a[p];
    map<int, int> b;
    int n = 0;
    for (int i = 0; i < p; i++) {
        scanf("%d", &a[i]);
        if (b[a[i]] == 0) {
            n++;
        }
        b[a[i]]++;
    }
    int s = 0;
    int t = 0;
    int ans = p;
    int num = 0;
    b.clear();
    for (; ; ) {
        while (t < p && num < n) {
            if (b[a[t]] == 0) {
                num++;
            }
            b[a[t++]]++;
        }
        if (num < n) {
            break;
        }
        while (b[a[s]] > 1) {
            b[a[s]]--;
            s++;
        }
        ans = min(ans, t-s);
        b[a[s++]]--;
        num--;
    }
    cout << ans << endl;
    return 0;
}<file_sep>/blocks.cpp
#include<stdio.h>
typedef long long ll;

ll pow(ll x, ll n){
    ll ans = 1;
    while (n > 0) {
        if (n & 1) {
            ans = ans * x;
        }
        x = x * x;
        n >>= 1;
    }
    return ans;
}

ll getPar(ll n){
    ll res = 0;
    for (int i = 0; i*2 <= n; i++) {
        ll left = n-i*2;
        res += pow(2, left);
    }
    return res;
}


int main(){
    int n;
    scanf("%d", &n);
    ll ans = 0;
    for (int i = 0; i*2 <= n; i++) {
        ans += getPar(n-i*2);
    }
    printf("%lld\n", ans);
    return 0;
}<file_sep>/fence_repair.cpp
#include<iostream>
#include<queue>
using namespace std;
priority_queue<int> L;
long long ans = 0;

void rec(){
    if (L.size() <= 1) {
        return;
    }
    int a = L.top();
    L.pop();
    int b = L.top();
    L.pop();
    ans += -(a+b);
    L.push(a+b);
    rec();
}


int main(){
    int n;
    cin >> n;
    
    int a;
    for (int i = 0; i < n; i++) {
        cin >> a;
        L.push(a*(-1));
    }
    rec();
    cout << ans << endl;
    return 0;
}<file_sep>/crane.cpp
#include<stdio.h>
#define _USE_MATH_DEFINES
#include <cmath>
#define MAX_N 10001

using namespace std;
const int ST_SIZE = (1 << 15) -1;

double vx[ST_SIZE], vy[ST_SIZE];
double ang[ST_SIZE];
int s[MAX_N];
double prv[MAX_N];
int n;

void init(int i, int l, int r){
    ang[i] = 0.0;
    vx[i] = 0.0;
    if (r-l == 1) {
        vy[i] = s[l];
        return;
    }else{
        init(i*2+1, l, (r+l)/2);
        init(i*2+2, (r+l)/2, r);
        vy[i] = vy[i*2+1] + vy[i*2+2];
    }
}

void change(int i, double a, int k, int l, int r){
    printf("i:%d  a:%lf  k:%d  l:%d  r:%d\n", i, a, k, l, r);
    if (i <= l) {
        return;
    }else if(i < r){
        int chl = k*2+1;
        int chr = k*2+2;
        change(i, a, chl, l, (l+r)/2);
        change(i, a, chr, (l+r)/2, r);
        if (i <= (l+r)/2) {
            ang[k] += a;
            printf("k:%d  ang[k]:%lf\n", k, ang[k]);
        }
        
        double cosin = cos(ang[k]);
        double sine = sin(ang[k]);
        
        vx[k] = vx[chl] + cosin*vx[chr]-sine*vy[chr];
        vy[k] = vy[chl] + sine*vx[chr]+cosin*vy[chr];
    }
}

int main(){
    int c;
    while(scanf("%d %d", &n, &c) != EOF){
        for (int i = 0; i < n; i++) {
            scanf("%d", &s[i]);
            prv[i] = M_PI;
        }
        init(0, 0, n);
        for (int i = 0; i < n; i++) {
            printf("%lf %lf %lf\n", vx[i], vy[i], ang[i]);
        }
        int num;
        double a;
        for (int i = 0; i < c; i++) {
            scanf("%d %lf", &num, &a);
            double avg = a/180.0*M_PI;
            change(num, avg-prv[num],  0, 0, n);
            prv[num] = avg;
            printf("%.2f %.2f\n", vx[0], vy[0]);

        }
    }
    return 0;
}<file_sep>/fast_evacuation.cpp
#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
#include<string.h>
using namespace std;
#define MAX_Y 15
#define MAX_X 15
#define MAX_V 15*15*100
char field[MAX_X][MAX_Y];
vector<int> dX, dY;
vector<int> pX, pY;
int dist[MAX_X][MAX_Y][MAX_X][MAX_Y];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int X, Y;
vector<int> G[MAX_V];
int match[MAX_V];
bool used[MAX_V];

void add_edge(int i, int u){
    G[i].push_back(u);
    G[u].push_back(i);
}

bool dfs(int i){
    used[i] = true;
    for (int j = 0; j < G[i].size(); j++) {
        int u = G[i][j], w = match[u];
        if (w < 0 || (!used[w] && dfs(w))) {
            match[i] = u;
            match[u] = i;
            return true;
        }
    }
    return false;
}


void bfs(int x, int y, int d[MAX_X][MAX_Y]){
    queue<int> qx, qy;
    d[x][y] = 0;
    qx.push(x);
    qy.push(y);
    while(!qx.empty()){
        int nx = qx.front();
        qx.pop();
        int ny = qy.front();
        qy.pop();
        for(int i = 0; i < 4; i++){
            int nextx = nx+dx[i], nexty = ny+dy[i];
            if (nextx >= 0 && nextx < X && nexty >= 0 && nexty < Y && field[nextx][nexty] == '.' && d[nextx][nexty] < 0){
                d[nextx][nexty] = d[nx][ny]+1;
                qx.push(nextx);
                qy.push(nexty);
            }
        }
    }
}


void solve(){
    int n = X*Y;
    dX.clear();
    dY.clear();
    pX.clear();
    pY.clear();
    memset(dist, -1, sizeof(dist));
    
    for (int i = 0; i < MAX_V; i++) {
        G[i].clear();
    }
    for (int x = 0; x < MAX_X; x++) {
        for (int y = 0; y < MAX_Y; y++) {
            if (field[x][y] == 'D') {
                dX.push_back(x);
                dY.push_back(y);
                bfs(x, y, dist[x][y]);
            }else if(field[x][y] == '.'){
                pX.push_back(x);
                pY.push_back(y);
            }
        }
    }
    int d = dX.size(), p = pX.size();

    for (int i = 0; i < d; i++) {
        for (int j = 0; j < p; j++) {
            if (dist[dX[i]][dY[i]][pX[j]][pY[j]] >= 0) {
                for (int k = dist[dX[i]][dY[i]][pX[j]][pY[j]]; k <= n; k++) {
                    add_edge((k-1)*d+i, n*d+j);
                }
            }
        }
    }
    if (p == 0) {
        printf("0\n");
        return;
    }
    int res = 0;
    memset(match, -1, sizeof(match));
    for (int i = 0; i < n*d; i++) {
        memset(used, 0, sizeof(used));
        if (dfs(i)) {
            if (++res == p) {
                printf("%d\n", (i / d + 1));
                return;
            }
        }
        
    }
    printf("impossible\n");
}

int main(){
    int t;
    scanf("%d", &t);
    for (int j = 0; j < t; j++) {
        scanf("%d %d", &X, &Y);
        memset(field, 'X', sizeof(field));
        for(int i = 1; i <= X; i++){
            scanf("%s", &field[i][1]);
        }
        solve();

    }
    return 0;
}
<file_sep>/k-th_number.cpp
#include<stdio.h>
#include<vector>
#include<algorithm>
#define MAX_N 100000
#define B 1000

using namespace std;
int a[MAX_N];
int num[MAX_N];
vector<int> bucket[MAX_N/B];

int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        num[i] = a[i];
        bucket[i/B].push_back(num[i]);
    }
    sort(num, num+n);
    for (int i = 0; i < n/B; i++) {
        sort(bucket[i].begin(), bucket[i].end());
    }
    int i, j, k;
    for (int t = 0; t < m; t++) {
        scanf("%d%d%d", &i, &j, &k);
        i--;
        int lb = -1;
        int ub = n-1;
        while(ub - lb > 1){
            int mid = (lb+ub)/2;
            int x = num[mid];
            int tl = i, tr = j, c = 0;
            while (tr > tl && tl%B != 0) {
                if (a[tl++] <= x) {
                    c++;
                }
            }
            while (tr > tl && tr%B != 0) {
                if (a[--tr] <= x ) {
                    c++;
                }
            }
            while (tl < tr) {
                int b = tl/B;
                c += upper_bound(bucket[b].begin(), bucket[b].end(), x) - bucket[b].begin();
                tl += B;
            }
            if (c >= k) {
                ub = mid;
            }else{
                lb = mid;
            }
        }
        printf("%d\n", num[ub]);
    }
    return 0;
}
<file_sep>/fliptile_model.cpp
#include<iostream>
#include<stdio.h>
#include<string.h>
#define M 15
#define N 15
using namespace std;
int m, n;

int x[5] = {-1, 0,0, 0 ,1 };
int y[5] = {0,-1, 0, 1, 0 };
int flip[M][N];
int tile[M][N];
int res = -1;
int opt[M][N];

bool whilteOrNot(int i, int j){
    int c = tile[i][j];
    for (int k = 0; k < 5; k++) {
        int x2 = i+x[k], y2 = j+y[k];
        if (x2 >= 0 && x2 < m && y2 >= 0 && y2 < n) {
            c += flip[x2][y2];
        }
    }
    return c%2;
}

int cal(){
    int a = 0;
    for (int i = 1; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (whilteOrNot(i-1, j) != 0) {
                flip[i][j] = 1;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        if (whilteOrNot(m-1, i) != 0) {
            return -1;
        }
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (flip[i][j] == 1) {
                a++;
            }
        }
    }
    return a;
}

bool check(){
    for (int i = 0; i < n; i++) {
        if ((tile[m-1][i]+flip[m-1][i])%2!=0) {
            return false;
        }
    }
    return true;
}



int main(){
    cin >> m >> n;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &tile[i][j]);
        }
    }
    for (int i = 0; i < 1 << n; i++) {
        memset(flip, 0, sizeof(flip));
        for (int j = 0; j < n; j++) {
            int a = n-1-j;
            int b = i >> j & 1;
            flip[0][a] = b;
        }
        int num = cal();
        if (num >= 0 && (num < res || res < 0)) {
            res = num;
            memcpy(opt, flip, sizeof(flip));
        }
    }
    if (res < 0) {
        cout << "IMPOSSIBLE" << endl;
    }else{
        for (int j = 0; j < m; j++) {
            for (int k = 0; k < n; k++) {
                printf("%d%c", opt[j][k], k+1==n ? '\n' : ' ');
            }
        }
    }
    return 0;
}<file_sep>/subsequence.cpp
#include<stdio.h>
#include<algorithm>
using namespace std;

int main(){
    int t;
    scanf("%d", &t);
    for (int i = 0; i < t; i++) {
        int n, s;
        scanf("%d%d", &n, &s);
        int a[n];
        for (int j = 0; j < n; j++) {
            scanf("%d",&a[j]);
        }
        int head = 0;
        int sum = 0;
        int ans = n+1;
        int j = 0;
//        for (;;) {
//            while (j < n&& sum < s) {
//                sum += a[j++];
//            }
//            if (sum < s) {
//                break;
//            }
//            ans = min(ans, j-head);
//            sum -= a[head++];
//        }
        for (j = 0;j < n;j++) {
            sum+=a[j];
            if (sum < s) {
                
            }else if(sum == s){
                ans = min(ans, j-head+1);
            }else {
                while (sum - a[head] > s) {
                    sum -= a[head];
                    head++;
                }
                ans = min(ans, j-head+1);
            }
            
        }
        
        if (ans > n) {
            ans = 0;
        }
        printf("%d\n",ans);
    }
    return 0;
}<file_sep>/saruman_army.cpp
#include<iostream>
#include<algorithm>
using namespace std;
#define N 1000

int main(){
    int n, R;
    int x[N];
    while (1) {
        cin >> R >> n;
        if (n == -1 && R == -1) {
            break;
        }
        for (int i = 0; i < n; i++) {
            cin >> x[i];
        }
        sort(x, x+n);
        int i = 0;
        int prev = 0;
        int ans = 0;
        while (i < n) {
            prev = x[i++];
            while (i < n && x[i] - prev <= R) {
                i++;
            }
            prev = x[i-1];
            while (i < n && x[i] - prev <= R) {
                i++;
            }
            ans++;
        }
        cout << ans << endl;
    }
    return 0;
}