Submission #1208366

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208366		Belphegor	Painting Squares (IOI20_squares)	C++20	0 / 100	28 ms	568 KiB

squares

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pi;
vector<pi>graph[2222];
bool used[2222];
int idx[2222];
vector<int>v,path;

void DFS(int cur,int edg){
	while(graph[cur].size()){
		int nxt = graph[cur].back().first;
		int e = graph[cur].back().second;
		graph[cur].pop_back();
		if(used[e]) continue;
		used[e] = 1;
		DFS(nxt,e);
	}
	v.emplace_back(edg);
}
void construct_path(int n){
	int mask = (1<<n)-1; mask>>=1;
	for(int i=0; i<(1<<n); i++){
		int from = i>>1;
		int to = i&mask;
		graph[from].emplace_back(pi(to,i));
	}
	DFS(1,-1);
	v.pop_back();
	reverse(v.begin(),v.end());
	
	for(int i=0; i<v.size(); i++){
		int a = v[i];
		vector<int>vec;
		for(int j=n-1; j>=0; j--){
			if(a&(1<<j)) vec.emplace_back(1);
			else vec.emplace_back(0);
		}
		if(path.empty()){
			for(int z : vec) path.emplace_back(z);
		}
		else path.emplace_back(vec.back());
	}
	for(int i=0; i+9<path.size(); i++){
		int val = 0;
		for(int j=0; j<10; j++) val = val*2+path[i+j];
		idx[val] = i;
	}
}
std::vector<int> paint(int n){
	if(v.empty()) construct_path(10);
	std::vector<int> labels(n + 1, 1);
	for(int i=0; i<n; i++) labels[i] = path[i];
	labels[n] = (n >= 10?10:n);
	return labels;
}

int find_location(int n, std::vector<int> c) {
	int cnt = 0;
	for(int x : c) cnt += (x == -1);
	if(cnt) return n-c.size()+cnt;
	if(n < 10) return 0;
    assert(c.size() == 10);
	int val = 0;
	for(int x : c) val = val*2 + x;
	return idx[val];
}

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