Submission #1193764

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193764		chaeryeong	Painting Squares (IOI20_squares)	C++20	0 / 100	0 ms	488 KiB

squares

#include "squares.h"
#include <bits/stdc++.h>
using namespace std;
vector <int> get (int k) {
	k--;
	set <int> adj[1 << k];
	auto add_edge = [&] (int x, int y) -> void {
		adj[x].insert(y);
	};
	for (int i = 0; i < (1 << k); i++) {
		add_edge(i / 2, i);
		add_edge((i / 2) + (1 << (k - 1)), i);
	}
	vector <int> ans;
	stack <int> cur;
	cur.push(0);
	while (!cur.empty()) {
		auto k = cur.top();
		if (adj[k].empty()) {
			ans.push_back(k);
			cur.pop();
		} else {
			auto v = *(--adj[k].end());
			adj[k].erase(v);
			cur.push(v);
		}
	}
	reverse(ans.begin(), ans.end());
	vector <int> ret;
	for (int i = 0; i - 1 < k; i++) {
		ret.push_back(0);
	}
	for (int i = 1; i < (int)ans.size(); i++) {
		ret.push_back(ans[i] & 1);
	}
	ret.pop_back();
	return ret;
}
std::vector<int> paint (int n) {
	int k = 1;
	while ((1 << k) + k - 1 < n) {
		k++;
	}
	auto g = get(k);
	while (g.size() > n) g.pop_back();
	g.push_back(k);
	return g;
}

int find_location(int n, std::vector<int> c) {
	if (c.back() == -1) {
		int cnt = 0;
		for (auto i : c) {
			cnt += i == -1;
		}
		return n - ((int)c.size() - cnt);
	}
	int k = 1;
	while ((1 << k) + k - 1 < n) {
		k++;
	}
	auto g = get(k);
	for (int i = 0; i < n; i++) {
		int flag = 1;
		for (int j = 0; j < k; j++) {
			flag &= g[i + j] == c[j];
		}
		if (flag) {
			return i;
		}
	}
	assert(0);
	return 0;
}

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