Submission #371618

#	Time	Username	Problem	Language	Result	Execution time	Memory
371618		hoaphat1	Painting Squares (IOI20_squares)	C++17	100 / 100	246 ms	468 KiB

squares

#include<bits/stdc++.h>

using namespace std;

vector<int> fpm;
vector<int> value;

void recall() {
	int k = 10;
	for (int i = 0; i < 10; i++) fpm.push_back(1);
	int v = (1 << k) - 1;
	vector<bool> kt(1 << k);
	kt[v] = true;
	while ((int)fpm.size() < 1000) {
		v = (v << 1) % (1 << k);
		int sign = 0;
		if (kt[v]) {
			v++;
			sign = 1;
		}
		assert(!kt[v]);
		kt[v] = true;
		value.push_back(v);
		fpm.push_back(sign);
	}
}

vector<int> paint(int n) {
	if (fpm.empty()) recall();
	vector<int> a(n + 1);
	a[n] = 10;
	for (int i = 0; i < n; i++) a[i] = fpm[i];
	return a;
}

vector<int> now;
int find_location(int n, vector<int> c) {
	if (fpm.empty()) recall();
	/*for (int i = 0; i < 10; i++) cout << c[i] <<" ";cout << endl;
	for (int i = 0; i < 10; i++) cout << need[i] <<" ";cout << endl;*/
	for (int i = 0; i < n; i++) {
		now.clear();
		for (int j = 0; j < 10; j++) {
			if (i + j >= n) now.push_back(-1);
			else now.push_back(fpm[i + j]);
		}
		if (now == c) return i;
	}
	assert(false);
}


/*int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n = 100;
	int* a = paint(n);
	//for (int i = 0; i <= n; i++) cout << a[i] <<" ";cout << endl;
	mt19937 rgn(chrono::steady_clock::now().time_since_epoch().count());
	for (int i = 0; i < 7; i++) {
		int pos = rgn() % n;
		int c[a[n]];
		for (int j = 0; j < a[n]; j++) {
			c[j] = (pos + j >= n ? -1 : a[pos + j]);
		}
		cout << pos << endl;
		cout << find_location(n, c) << endl;
	}
}*/

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