제출 #430515

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
430515		cfalas	Painting Squares (IOI20_squares)	C++14	0 / 100	3214 ms	1730704 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;

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

int mem[2000];

int ans;
void rec(int x){
	//cout<<"x "<<x<<endl;
	if(bcnt(x)==n){ ans=x; return; }

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

	int next = c*2 % (1<<ss);
	if(!all.count(next)) rec(x*2);
	if(ans) return;
	if(!all.count(next+1)) rec(x*2+1);

}

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

	rec(1<<(ss-1));
	
	vector<int> l;
	while(ans) l.push_back(ans%2), ans/=2;
	reverse(l.begin(), l.end());
	/*
	FOA(v,l) cout<<v<<" ";
	cout<<endl;
	cout<<endl;
	*/

	l.push_back(ss);
	return l;
}

int find_location(int n, std::vector<int> f) {
	ans=0;
	ss = bcnt(n);
	//cout<<"finding "<<endl;
	if(!mem[ss]) rec(1<<(bcnt(n)-1)), mem[ss] = ans;
	ans = mem[ss];
	//cout<<endl;
	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=bcnt(ans);
	int c=0;
	ind=-ss;
	while(i>=0){
		c = c*2 % (1<<ss);
		//cout<<"( "<<c<<" ";
		if(ans&(1<<i)) c++;
		//cout<<c<<") ";
		if(ind>=0 && x==c) return ind;
		ind++;
		i--;
	}
	//cout<<endl;
	return -1;
}

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