Submission #29662

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
29662	2017-07-20T10:05:37 Z	cdemirer	Question (Grader is different from the original contest) (CEOI14_question_grader)	C++14	100 / 100	1859 ms	25684 KB

encoder

#include <stdio.h>
#include <stdlib.h>
int tbl[921] = {0};

int next(int x) {
	int t = x;
	int lsb = t & -t;
	if (lsb != 1) {
		return t - lsb/2;
	}
	t -= t & -t;
	lsb = t & -t;
	if (lsb != 2) {
		return t - lsb/2 + lsb/4;
	}
	t -= t & -t;
	lsb = t & -t;
	if (lsb != 4) {
		return t - lsb/2 + lsb/4 + lsb/8;
	}
	t -= t & -t;
	lsb = t & -t;
	if (lsb != 8) {
		return t - lsb/2 + lsb/4 + lsb/8 + lsb/16;
	}
	t -= t & -t;
	lsb = t & -t;
	if (lsb != 16) {
		return t - lsb/2 + lsb/4 + lsb/8 + lsb/16 + lsb/32;
	}
	t -= t & -t;
	lsb = t & -t;
	if (lsb != 32) {
		return t - lsb/2 + lsb/4 + lsb/8 + lsb/16 + lsb/32 + lsb/64;
	}
	puts("Error! Please don't call next(int) more than 923 times again");
	exit(-1);
}

int encode (int n, int x, int y) {
	int num = 2048 | 1024 | 512 | 256 | 128 | 64;
	if (tbl[5] == 0) for (int i = 1; i < 921; i++) {
		tbl[i] = num;
		num = next(num);
	}
	int cnt = 0;
	x = tbl[x];
	y = tbl[y];
	while (true) {
		if (x % 2 == 1 && y % 2 == 0) {
			return cnt+1;
		}
		x >>= 1;
		y >>= 1;
		cnt++;
	}
}

decoder

#include <stdio.h>
#include <stdlib.h>
int tbl2[921] = {0};

int next2(int x) {
	int t = x;
	int lsb = t & -t;
	if (lsb != 1) {
		return t - lsb/2;
	}
	t -= t & -t;
	lsb = t & -t;
	if (lsb != 2) {
		return t - lsb/2 + lsb/4;
	}
	t -= t & -t;
	lsb = t & -t;
	if (lsb != 4) {
		return t - lsb/2 + lsb/4 + lsb/8;
	}
	t -= t & -t;
	lsb = t & -t;
	if (lsb != 8) {
		return t - lsb/2 + lsb/4 + lsb/8 + lsb/16;
	}
	t -= t & -t;
	lsb = t & -t;
	if (lsb != 16) {
		return t - lsb/2 + lsb/4 + lsb/8 + lsb/16 + lsb/32;
	}
	t -= t & -t;
	lsb = t & -t;
	if (lsb != 32) {
		return t - lsb/2 + lsb/4 + lsb/8 + lsb/16 + lsb/32 + lsb/64;
	}
	puts("Error! Please don't call next(int) more than 923 times again");
	exit(-1);
}

int decode (int n, int q, int h) {
	int num = 2048 | 1024 | 512 | 256 | 128 | 64;
	if (tbl2[5] == 0) for (int i = 1; i < 921; i++) {
		tbl2[i] = num;
		num = next2(num);
	}
	q = tbl2[q];
	h -= 1;
	while (h--) q >>= 1;
	return q % 2 == 1;
};

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1632 ms	25684 KB	Output is correct - maxh = 12
2	Correct	1859 ms	25684 KB	Output is correct - maxh = 12