1977.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1977 on 2005-10-01 at 22:23:49 */ 
#include <cstdio>
#include <cstring>
#define  MAX  500000

class BitVector {
public:
	unsigned char c[380000];
	BitVector() {
		memset(c, 0, sizeof(c));
	}
	void set(long index) {    
		c[byteNumber(index)] |= mask(index);
	}
	bool test(long index) {
		int i = c[byteNumber(index)] & mask(index);
		if(i == 0) {
			return false;
		} else {
			return true;
		}
	}
	long mask(long index) {
		return 1 << (index & 07);
	}
	long byteNumber(long index) {
		return index >> 3;
	}
};

int main()
{
	BitVector *bv = new BitVector();
	long a[MAX+1], p, k, i;
	
	a[0] = 0;
	for(i = 1; i <= 500000; i++) {
		p = a[i-1] - i;
		if(p > 0 && !(bv->test(p))) {
			bv->set(p);
			a[i] = p;
		} else {
			a[i] = a[i-1] + i;
			bv->set(a[i-1] + i);
		}
	}
	while(scanf("%ld", &k) == 1) {
		if(k == -1) {
			return 0;
		} else {
			printf("%ld\n", a[k]);
		}
	}
	
	return 0;
}