Submission #1189498

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189498		gyg	Painting Squares (IOI20_squares)	C++20	100 / 100	591 ms	472 KiB

squares

#include "squares.h"
#include <bits/stdc++.h>
using namespace std;
#define arr array 
#define vec vector
const int N = 2e3 + 5;

vec<int> ord;
arr<bool, N> vs;
void intl() {
	ord.clear(), vs.fill(false);
}
void dfs(int k, int u = 0) {
	vs[u] = true, ord.push_back(u);
	int v = (2 * u + 1) % (1 << k), w = (2 * u) % (1 << k);
	if (!vs[v]) dfs(k, v);
	else if (!vs[w]) dfs(k, w);
}

vec<int> slv(int n) {
	int k = min(10, n);
	intl(), dfs(k);

	vec<int> ans;
	auto on = [](int x, int i)->bool { return x & (1 << i); };
	for (int i = k - 1; i >= 0; i--)
		ans.push_back(on(ord[0], i));
	for (int i = 1; i <= n - k; i++)
		ans.push_back(on(ord[i], 0));
	return ans;
}

vec<int> paint(int n) {
	vec<int> ans = slv(n);
	int k = min(10, n);
	ans.push_back(k);
	return ans;
}

int find_location(int n, vec<int> rq) {
	vec<int> sq = slv(n);
	int k = min(10, n);

	for (int i = 0; i < n; i++) {
		vec<int> cr;
		for (int j = i; j <= i + k - 1; j++) 
			cr.push_back((j >= n) ? -1 : sq[j]);
		if (cr == rq) return i;
	}
	assert(false); return -1;
}

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