Andrew Stankevich’s Contest #3解题报告 » ZOJ2363

ZOJ2363
ZOJ2363.cpp


#include <set>
#include <cstdio>
#include <vector>

using namespace std;

int bitLength(int m) {
	int ret = 0;
	while (m > 0) {
		m >>= 1;
		++ret;
	}
	return ret;
}

#define CHANGE(p, d) \
	do {\
		if (v[p] == 0) {\
			zero.erase(p);\
		} else if (v[p] == 2) {\
			two.erase(p);\
		}\
		v[p] += d;\
		printf(" %d %d", p, v[p]);\
		if (v[p] == 0) {\
			zero.insert(p);\
		} else if (v[p] == 2) {\
			two.insert(p);\
		}\
	} while(false)

int main() {
	int re;
	int n, m, p;

	scanf("%d", &re);
	for (int ri = 1; ri <= re; ++ri) {
		if (ri > 1) {
			puts("");
		}
		scanf("%d%d", &n, &m);
		vector<int> v(n + bitLength(m), 0);
		set<int> zero;
		set<int> two;
		set<int>::iterator iz, it;
		for (int i = 0; i < (int)v.size(); ++i) {
			zero.insert(i);
		}
		two.insert((int)v.size());
		for (int i = 0; i < m; ++i) {
			scanf("%d", &p);
			it = two.upper_bound(p);
			iz = zero.upper_bound(*it);
			--iz;
			if (p >= *iz) {
				putchar('3');
				CHANGE(p, +1);
				CHANGE(*it, -2);
				CHANGE(*it + 1, +1);
			} else if (v[p] > 0) {
				putchar('2');
				CHANGE(p, -1);
				CHANGE(p + 1, +1);
			} else {
				putchar('1');
				CHANGE(p, +1);
			}
			putchar('\n');
		}
	}

	return 0;
}
//Run ID  	Submit Time  	Judge Status  	Problem ID  	Language  	Run Time(ms)  	Run Memory(KB)  	User Name
//1828490 	2009-04-11 03:59:33 	Accepted 	2363 	C++ 	210 	176 	watashi@Zodiac
Leave a Reply