UVa1607 poj1435 UVaLive1686 Gates

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<algorithm>

 #include<iostream>

 using namespace std;

 void setIO(const string& s) {

     freopen((s + ".in").c_str(), "r", stdin);

     freopen((s + ".out").c_str(), "w", stdout);

 }

 template<typename Q> Q read(Q& x) {

     static char c, f;

     for(f = ; c = getchar(), !isdigit(c); ) if(c == '-') f = ;

     for(x = ; isdigit(c); c = getchar()) x = x *  + c - '';

     if(f) x = -x;

     return x;

 }

 template<typename Q> Q read() {

     static Q x; read(x); return x;

 }

 const int N =  + ;

 int n, m;

 struct Gates {

     int a, b, o;

 }gates[N];

 int output(int k) {

     for(int i = ; i <= m; i++) {

         int a = gates[i].a;

         int b = gates[i].b;

         int va = a <  ? -a > k : gates[a].o;

         int vb = b <  ? -b > k : gates[b].o;

         gates[i].o = !(va && vb);

     }

     return gates[m].o;

 }

 int solve(int vn) {

     int L = , R = n;

     while(L < R) {

         int mid = L + (R - L) / ;

         if(output(mid) == vn) R = mid; else L = mid + ;

     }

     return L;

 }

 int main() {

 #ifdef DEBUG

     freopen("in.txt", "r", stdin);

     freopen("out.txt", "w", stdout);

 #endif

     int T; scanf("%d", &T);

     while(T--) {

         scanf("%d%d", &n, &m);

         for(int i = ; i <= m; i++) {

             scanf("%d%d", &gates[i].a, &gates[i].b);

         }

         int v0 = output(), vn = output(n);

         if(v0 == vn) for(int i = ; i <= n; i++) putchar('');

         else {

             int p = solve(vn);

             for(int i = ; i < p; i++) putchar('');

             putchar('x');

             for(int i = p + ; i <= n; i++) putchar('');

         }

         puts("");

     }

     return ;

 }