紫书 例题8-14 UVa 1607 （二分）

题意非常难理解……

#include<cstdio>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

const int MAXN = 212345;

struct node

{

	int a, b, w;

}g[MAXN];

int n, m;

int output(int k)

{

	REP(i, 1, m + 1)

	{

		int a = g[i].a;

		int b = g[i].b;

		int va = a < 0 ? -a > k : g[a].w;

		int vb = b < 0 ? -b > k : g[b].w;

		g[i].w = !(va && vb);

	}

	return g[m].w;

}

int solve(int vn)

{

	int l = 0, r = n + 1;

	while(l + 1 < r)

	{

		int mid = (l + r) >> 1;

		if(output(mid) == vn) r = mid;

		else l = mid;

	}

	return r;

}

int main()

{

	int T;

	scanf("%d", &T);

	while(T--)

	{

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

		REP(i, 1, m + 1) scanf("%d%d", &g[i].a, &g[i].b);

		int v0 = output(0);

		int vn = output(n);

		if(v0 == vn)

		{

			REP(i, 1, n + 1) putchar('0');

			puts(""); continue;

		}

		int x = solve(vn);

		REP(i, 1, x) putchar('0');

		putchar('x');

		REP(i, x + 1, n + 1) putchar('1');

		puts("");

	}

	return 0;

}