Submission #429932

#	Time	Username	Problem	Language	Result	Execution time	Memory
429932		Kerim	Painting Squares (IOI20_squares)	C++17	100 / 100	374 ms	728 KiB

squares

#include "squares.h"
#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

const int N=10;
string str;
int vis[1<<N][2],idx[1<<N];
void dfs(int mask){
	mask&=(1<<(N-1))-1;
	for(int i=0;i<2;i++)
		if(!vis[mask][i]){
			vis[mask][i]=1;
			dfs((mask<<1)|i);
			str+='0'+i;
		}
}
void build(){
	str.clear();
	memset(vis,0,sizeof vis);
	memset(idx,0,sizeof idx);
	dfs(0);
	int n=str.size();
	for(int i=0;i<=n-N;i++){
		int mask=0;
		for(int j=0;j<N;j++)
			mask|=(1<<j)*(str[i+j]-'0');
		idx[mask]=i;
	}
}
vector<int> paint(int n) {
	build();
	vector<int> labels(n + 1, 1);
	for(int i=0;i<n;i++)
		labels[i]=str[i]-'0';
	labels[n]=N;
	return labels;
}

int find_location(int n, vector<int> c) {
	assert(int(c.size())==N);
	if(c[N-1]==-1){
		int ans=n-N,p=N-1;
		while(p>=0 and c[p]==-1)p--,ans++;
		return ans;
	}
	build();
	int mask=0;
	for(int j=0;j<N;j++)
		mask|=(1<<j)*c[j];
	return idx[mask];
}

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