Submission #1168355

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168355		12345678	Painting Squares (IOI20_squares)	C++20	100 / 100	27 ms	412 KiB

squares

#include "squares.h"
#include <bits/stdc++.h>

using namespace std;

const int k=10;

int t, vs[(1<<k)], init=0, dp[(1<<k)];
vector<int> v;

std::vector<int> paint(int n) {
	if (!init)
	{
		init=1;
		for (int i=0; i<k; i++) v.push_back(0);
		vs[0]=1;
		int lst=0;
		dp[lst]=0;
		for (int i=k; i<(1<<k); i++)
		{
			lst-=v[v.size()-k]*(1<<(k-1));
			lst=lst*2;
			if (!vs[lst+1]) lst++, dp[lst]=i-k+1, v.push_back(1), vs[lst]=1;
			else v.push_back(0), dp[lst]=i-k+1, vs[lst]=1;
		}
	}
	vector<int> res=v;
	while (res.size()>n) res.pop_back();
	res.push_back(k);
	return res;
}

int find_location(int n, std::vector<int> c) {
	if (!init)
	{
		init=1;
		for (int i=0; i<k; i++) v.push_back(0);
		vs[0]=1;
		int lst=0;
		dp[lst]=0;
		for (int i=k; i<(1<<k); i++)
		{
			lst-=v[v.size()-k]*(1<<(k-1));
			lst=lst*2;
			if (!vs[lst+1]) lst++, dp[lst]=i-k+1, v.push_back(1), vs[lst]=1;
			else v.push_back(0), dp[lst]=i-k+1, vs[lst]=1;
			//cout<<"debug "<<lst<<' '<<dp[lst]<<'\n';
		}
	}
	int cnt=0;
	for (auto x:c) if (x==-1) cnt++;
	if (cnt) return n-k+cnt; 
	for (int i=0; i<k; i++) cnt*=2, cnt+=c[i];
	return dp[cnt];
}

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