Submission #1043021

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043021		flappybird	Painting Squares (IOI20_squares)	C++17	0 / 100	1 ms	1532 KiB

squares

#include "squares.h"
#include <bits/stdc++.h>
using namespace std;


bool chk[101010];
bool chkc[101010];
int p[100];
int rev[101010];
int K = 2;
int M = 10;
void chkf(int x) {
	while (1) {
		if (chkc[x]) break;
		chkc[x] = 1;
		x = x / K + p[M - 1] * (x % K);
	}
}
int cnt;
void f(int v) {
	while (1) {
		rev[cnt++] = v / p[M - 1];
		chk[v] = 1;
		int c = v % K;
		int nv = v / K + p[M - 1] * ((c + 1) % K);
		if (!chkc[nv]) {
			chkf(nv);
			f(nv);
		}
		nv = v / K + p[M - 1] * c;
		if (chk[nv]) break;
		v = nv;
	}
}

std::vector<int> paint(int n) {
	memset(chk, 0, sizeof(chk));
	memset(chkc, 0, sizeof(chkc));
	memset(p, 0, sizeof(p));
	memset(rev, 0, sizeof(rev));
	int i;
	cnt = M - 1;
	p[0] = 1;
	for (i = 1; i < M; i++) p[i] = p[i - 1] * K;
	chk[0] = chkc[0] = 1;
	vector<int> v;
	f(0);
	for (i = n; i <= 2000; i++) rev[i] = -1;
	for (i = 0; i < n; i++) v.push_back(rev[i]);
	v.push_back(10);
	return v;
}

int find_location(int n, std::vector<int> c) {
	int i, j;
	for (i = 0; i < n + 20; i++) {
		int chk = 1;
		for (j = 0; j < 10; j++) {
			if (rev[i + j] != c[j]) {
				chk = 0;
				break;
			}
		}
		if (chk) return i;
	}
	assert(0);
	return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 55