Submission #430836

#	Time	Username	Problem	Language	Result	Execution time	Memory
430836		cfalas	Painting Squares (IOI20_squares)	C++14	100 / 100	159 ms	732 KiB

squares

#include <bits/stdc++.h>
using namespace std;
#define FORi(i,a,b) for(int i=(int)a;i<(int)b;i++)
#define FOR(i,n) FORi(i,0,n)
#define FOA(v, a) for(auto v : a)
#define ll long long
#define F first
#define S second
typedef pair<int, int> ii;
#include "squares.h"

int ss = 0;
int n;

vector<vector<int> > pre = {{0},{0,1}, {0,0,1,0}, {0,0,0,1,0,1,1,0}, {0,0,0,0,1,0,0,1,1,0,1,0,1,1,1,0}, {0,0,0,0,0,1,0,0,0,1,1,0,0,1,0,1,0,0,1,1,1,0,1,0,1,1,0,1,1,1,1,0}, {0,0,0,0,0,0,1,0,0,0,0,1,1,0,0,0,1,0,1,0,0,0,1,1,1,0,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,0,1,1,1,1,1,0}, {0,0,0,0,0,0,0,1,0,0,0,0,0,1,1,0,0,0,0,1,0,1,0,0,0,0,1,1,1,0,0,0,1,0,0,1,0,0,0,1,0,1,1,0,0,0,1,1,0,1,0,0,0,1,1,1,1,0,0,1,0,0,1,1,0,0,1,0,1,0,1,0,0,1,0,1,1,1,0,0,1,1,0,1,1,0,0,1,1,1,0,1,0,0,1,1,1,1,1,0,1,0,1,0,1,1,0,1,0,1,1,1,1,0,1,1,0,1,1,1,0,1,1,1,1,1,1,0}, {0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,1,1,0,0,0,0,1,0,0,1,0,0,0,0,1,0,1,1,0,0,0,0,1,1,0,1,0,0,0,0,1,1,1,1,0,0,0,1,0,0,0,1,0,0,1,1,0,0,0,1,0,1,0,1,0,0,0,1,0,1,1,1,0,0,0,1,1,0,0,1,0,0,0,1,1,0,1,1,0,0,0,1,1,1,0,1,0,0,0,1,1,1,1,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,1,1,0,0,1,0,1,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,1,1,0,0,1,1,0,0,1,1,0,1,0,1,0,0,1,1,0,1,1,1,0,0,1,1,1,0,1,1,0,0,1,1,1,1,0,1,0,0,1,1,1,1,1,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,1,0,1,1,0,1,0,1,1,1,1,1,0,1,1,0,1,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0}, {0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,1,1,1,0,0,0,0,0,1,0,0,1,0,0,0,0,0,1,0,1,1,0,0,0,0,0,1,1,0,1,0,0,0,0,0,1,1,1,1,0,0,0,0,1,0,0,0,1,0,0,0,0,1,0,0,1,1,0,0,0,0,1,0,1,0,1,0,0,0,0,1,0,1,1,1,0,0,0,0,1,1,0,0,1,0,0,0,0,1,1,0,1,1,0,0,0,0,1,1,1,0,1,0,0,0,0,1,1,1,1,1,0,0,0,1,0,0,0,1,1,0,0,0,1,0,0,1,0,1,0,0,0,1,0,0,1,1,1,0,0,0,1,0,1,0,0,1,0,0,0,1,0,1,0,1,1,0,0,0,1,0,1,1,0,1,0,0,0,1,0,1,1,1,1,0,0,0,1,1,0,0,1,1,0,0,0,1,1,0,1,0,1,0,0,0,1,1,0,1,1,1,0,0,0,1,1,1,0,0,1,0,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1,0,1,0,0,0,1,1,1,1,1,1,0,0,1,0,0,1,0,0,1,0,1,1,0,0,1,0,0,1,1,0,1,0,0,1,0,0,1,1,1,1,0,0,1,0,1,0,0,1,1,0,0,1,0,1,0,1,0,1,0,0,1,0,1,0,1,1,1,0,0,1,0,1,1,0,1,1,0,0,1,0,1,1,1,0,1,0,0,1,0,1,1,1,1,1,0,0,1,1,0,0,1,1,1,0,0,1,1,0,1,0,1,1,0,0,1,1,0,1,1,0,1,0,0,1,1,0,1,1,1,1,0,0,1,1,1,0,1,0,1,0,0,1,1,1,0,1,1,1,0,0,1,1,1,1,0,1,1,0,0,1,1,1,1,1,0,1,0,0,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,1,0,1,0,1,0,1,1,1,1,0,1,0,1,1,0,1,1,1,0,1,0,1,1,1,0,1,1,0,1,0,1,1,1,1,1,1,0,1,1,0,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,1,0,1,1,1,1,1,1,1,1,0}, {0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,1,0,1,1,0,0,0,0,0,0,1,1,0,1,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,0,1,1,0,0,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,1,1,1,0,0,0,0,0,1,1,0,0,1,0,0,0,0,0,1,1,0,1,1,0,0,0,0,0,1,1,1,0,1,0,0,0,0,0,1,1,1,1,1,0,0,0,0,1,0,0,0,0,1,0,0,0,1,1,0,0,0,0,1,0,0,1,0,1,0,0,0,0,1,0,0,1,1,1,0,0,0,0,1,0,1,0,0,1,0,0,0,0,1,0,1,0,1,1,0,0,0,0,1,0,1,1,0,1,0,0,0,0,1,0,1,1,1,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,1,1,0,0,1,1,0,0,0,0,1,1,0,1,0,1,0,0,0,0,1,1,0,1,1,1,0,0,0,0,1,1,1,0,0,1,0,0,0,0,1,1,1,0,1,1,0,0,0,0,1,1,1,1,0,1,0,0,0,0,1,1,1,1,1,1,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,1,1,1,0,0,0,1,0,0,1,0,0,1,0,0,0,1,0,0,1,0,1,1,0,0,0,1,0,0,1,1,0,1,0,0,0,1,0,0,1,1,1,1,0,0,0,1,0,1,0,0,1,1,0,0,0,1,0,1,0,1,0,1,0,0,0,1,0,1,0,1,1,1,0,0,0,1,0,1,1,0,0,1,0,0,0,1,0,1,1,0,1,1,0,0,0,1,0,1,1,1,0,1,0,0,0,1,0,1,1,1,1,1,0,0,0,1,1,0,0,0,1,1,0,0,1,0,1,0,0,0,1,1,0,0,1,1,1,0,0,0,1,1,0,1,0,0,1,0,0,0,1,1,0,1,0,1,1,0,0,0,1,1,0,1,1,0,1,0,0,0,1,1,0,1,1,1,1,0,0,0,1,1,1,0,0,1,1,0,0,0,1,1,1,0,1,0,1,0,0,0,1,1,1,0,1,1,1,0,0,0,1,1,1,1,0,0,1,0,0,0,1,1,1,1,0,1,1,0,0,0,1,1,1,1,1,0,1,0,0,0,1,1,1,1,1,1,1,0,0,1,0,0,1,0,0,1,1,0,0,1,0,0,1,0,1,0,1,0,0,1,0,0,1,0,1,1,1,0,0,1,0,0,1,1,0,1,1,0,0,1,0,0,1,1,1,0,1,0,0,1,0,0,1,1,1,1,1,0,0,1,0,1,0,0,1,0,1,0,0,1,1,1,0,0,1,0,1,0,1,0,1,1,0,0,1,0,1,0,1,1,0,1,0,0,1,0,1,0,1,1,1,1,0,0,1,0,1,1,0,0,1,1,0,0,1,0,1,1,0,1,0,1,0,0,1,0,1,1,0,1,1,1,0,0,1,0,1,1,1,0,1,1,0,0,1,0,1,1,1,1,0,1,0,0,1,0,1,1,1,1,1,1,0,0,1,1,0,0,1,1,0,1,0,0,1,1,0,0,1,1,1,1,0,0,1,1,0,1,0,1,0,1,0,0,1,1,0,1,0,1,1,1,0,0,1,1,0,1,1,0,1,1,0,0,1,1,0,1,1,1,0,1,0,0,1,1,0,1,1,1,1,1,0,0,1,1,1,0,0,1,1,1,0,1,0,1,1,0,0,1,1,1,0,1,1,0,1,0,0,1,1,1,0,1,1,1,1,0,0,1,1,1,1,0,1,0,1,0,0,1,1,1,1,0,1,1,1,0,0,1,1,1,1,1,0,1,1,0,0,1,1,1,1,1,1,0,1,0,0,1,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,1,0,1,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,1,0,1,0,1,1,0,1,1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,0,1,1,1,1,0,1,1,0,1,0,1,1,1,1,1,1,1,0,1,1,0,1,1,0,1,1,1,0,1,1,0,1,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0}};

int bcnt(int x){
	int cnt=0;
	while(x) cnt++, x/=2;
	return cnt;
}

vector<int> mem[2000];

vector<int> ans;
void rec(vector<int> x){
	//cout<<"x "<<x<<endl;
	if((int)x.size()==n){ ans=x; return; }

	// slide da windo
	set<int> all;
	int i=0;
	int c=0;
	int ind=-ss+1;
	//cout<<"P ";
	while(i<(int)x.size()){
		c = c*2 % (1<<ss);
		//cout<<"( "<<c<<" ";
		if(x[i]) c++;
		//cout<<c<<") ";
		if(ind>=0) /*cout<<c<<" ",*/ all.insert(c);
		ind++;
		i++;
	}
	//cout<<endl;
	//cout<<"all ";FOA(v, all) cout<<v<<" ";
	//cout<<endl;

	int next = c*2 % (1<<ss);
	x.push_back(0);
	if(!all.count(next)) all.insert(next), rec(x);
	if(ans.size()) return;
	all.erase(next);
	x.back() = 1;
	if(!all.count(next+1)) all.insert(next+1), rec(x);
	all.erase(next+1);

}

vector<int> paint(int N) {
	n = N;
	//ans.clear();
	ss = bcnt(n);
	//cout<<"ss "<<ss<<endl;

	vector<int> t(ss, 0);
	/*
	x =  t;
	all.clear();
	all.insert(0);
	rec();*/
	
	//FOA(v,ans) cout<<v<<" ";
	//cout<<endl;
	vector<int> ans;
	FOR(i,n) ans.push_back(pre[ss][i]);
	//FOA(v,ans) cout<<v<<" ";
	//cout<<endl;
	ans.push_back(ss);
	//cerr<<"PAINTED\n";
	return ans;
}

int qq=0;
int find_location(int N, std::vector<int> f) {
	n = N;
	ss = bcnt(n);
	vector<int> ans = pre[ss];
	//cout<<"finding "<<endl;
	/*
	if(!mem[n].size()){
		vector<int> t(bcnt(n), 0);
		ans.clear();
		x  = t;
		all.clear();
		all.insert(0);
		rec();
		mem[n] = ans;
	}
	else{
		ans = mem[n];
	}*/
	int x =0;
	int ind=0;
	FOA(v,f){
		x*=2;
		x+=v;
		if(v==-1) return n-ind;
		ind++;
	}
	//cout<<"target "<<x<<endl;

	int i=0;
	int c=0;
	ind=-ss+1;
	while(i<(int)ans.size()){
		assert(ind<=n);
		c = c*2 % (1<<ss);
		//cout<<"( "<<c<<" ";
		if(ans[i]) c++;
		//cout<<c<<") ";
		//cout<<ind<<" "<<c<<" "<<x<<endl;
		if(ind>=0 && x==c) return ind;
		ind++;
		i++;
	}
	//cout<<endl;
	return -1;
}

/*
int main(){
	FORi(i,1,11){
		ans.clear();
		vector<int> x = vector<int>(i,0);
		ss = i;
		n = (1<<i);
		rec(x);
		FOA(v,ans) cout<<v<<" ";
		cout<<endl;
	}
}
*/

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