제출 #430818

#제출 시각아이디문제언어결과실행 시간메모리
430818cfalasPainting Squares (IOI20_squares)C++14
0 / 100
151 ms924 KiB
#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,0,1,1},{0,0,0,0,1,0,0,0,1,1,0,0,1,1,1,0},{0,0,0,0,0,1,0,0,0,0,1,1,0,0,0,1,1,1,0,0,1,0,1,0,0,1,1,1,1,0,1,0},{0,0,0,0,0,0,1,0,0,0,0,0,1,1,0,0,0,0,1,1,1,0,0,0,1,0,1,0,0,0,1,1,1,1,0,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,1,1,1,1,0,1,0,1,0,1,1,1},{0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,1,1,1,0,0,0,0,1,0,1,0,0,0,0,1,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,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,1,0,1,0,1,0,1,1,0,1,0,1,1,1,1,0,1,1},{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,1,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,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,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,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,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},{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,1,1,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,1,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,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,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,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,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},{0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,1,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,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,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,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,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,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}}; int bcnt(int x){ int cnt=0; while(x) cnt++, x/=2; return cnt; } vector<int> mem[2000]; vector<int> ans; vector<int> x; set<int> all; void rec(){ //cout<<"x "<<x<<endl; if((int)x.size()==n){ ans=x; return; } // slide da windo int i=0; int c=0; int ind=-ss+1; while(i<(int)x.size()){ c = c*2 % (1<<ss); //cout<<"( "<<c<<" "; if(x[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); x.push_back(0); if(!all.count(next)) all.insert(next), rec(); if(ans.size()) return; all.erase(next); x.back() = 1; if(!all.count(next+1)) all.insert(next+1), rec(); 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; ans.push_back(ss); cerr<<"PAINTED\n"; return ans; } int qq=0; int find_location(int N, std::vector<int> f) { qq++; if(qq%100==0) cout<<qq<<endl; n = N; ss = bcnt(n); assert(ss<(int)pre.size()); 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(); x = vector<int>(i,0); ss = i; n = (1<<i); all.clear(); all.insert(0); rec(); FOA(v,ans) cout<<v<<" "; cout<<endl; } }*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...