Cod sursă (job #119207)

#include <stdio.h>
#include <ctype.h>
#define D_MAX 10000
#define N_MAX 50000
#define DEBUG 0
#define EDEBUG 0
#define EEDEBUG 0
#define BRANCH 10

int L[D_MAX], C[D_MAX];
char V[D_MAX];

typedef unsigned long long ull;
ull becoo[N_MAX / 64 + 1];
int step;

inline void advance()
{
	int w = step / 64 + 1;
	ull carry = 0;
	for (int i = 0; i < w; ++i) {
		ull aux = becoo[i];
		becoo[i] ^= ((becoo[i] << 1) + carry);
		carry = aux >> 63;
	}
}

inline void advance2()
{
	int w = (step + 1) / 64 + 1;
	ull carry = 0;
	for (int i = 0; i < w; ++i) {
		ull aux = becoo[i];
		becoo[i] ^= ((becoo[i] << 2) + carry);
		carry = aux >> 62;
	}
}

inline int get(int pos)
{
	return 1 & (becoo[pos / 64] >> (pos % 64));
}

inline void set0(int pos)
{
	becoo[pos / 64] &= (~(1ull << (pos % 64)));
}

inline void set1(int pos)
{
	becoo[pos / 64] |= (1ull << (pos % 64));
}

#define BUF_SIZE 4096
char buf[BUF_SIZE];
int posc = BUF_SIZE;

inline char getChar(FILE *f) {
	if (posc == BUF_SIZE) {
		fread(buf, 1, BUF_SIZE, f);
		posc = 0;
	}
	return buf[posc++];
}

inline int readInt(FILE *f) {
	int result = 0;
	char c;
	do {
		c = getChar(f);
	} while (!isdigit(c));

	do {
		result = 10 * result + c - '0';
		c = getChar(f);
	} while (isdigit(c));

	return result;
}



int main()
{
	FILE *fin, *fout;
	fin = fopen("beculete.in", "r");
	fout = fopen("beculete.out", "w");

	int N = readInt(fin), D = readInt(fin);

	int i;
	for (i = 0; i < D; ++i) {
		L[i] = readInt(fin);
		C[i] = readInt(fin);
		V[i] = readInt(fin);
	}

	becoo[0] = 1;

	int sp = 0;
	L[D] = -1; // Santiela
	for (step = 1; step < N; ++step) {
		if (EDEBUG) {
			for (i = step - 1; i >= 0; i--) {
				printf("%d", get(i));
			}
			printf("\n");
		}
		if (BRANCH == 10) {
			if (step < N - 3 && L[sp] != step + 1) {
				advance2();
				++step;
			} else {
				advance();
			}
		} else {
			advance();
		}
		int step1 = step + 1;
		while (L[sp] == step1) {
			if (V[sp]) {
				set1(L[sp] - C[sp]);
			} else {
				if (DEBUG) {
					printf("Bec prost: %d %d\n", L[sp], C[sp]);
				}
				set0(L[sp] - C[sp]);
			}
			++sp;
		}
	}

	for (i = N - 1; i >= 0; --i) {
		fprintf(fout, get(i) ? "1 " : "0 ");
	}

	if (EEDEBUG) {
		for (i = N - 1; i >= 0; i--) {
			printf((get(i) ? "*" : "."));
		}
	}

	fclose(fin);
	fclose(fout);
}