제출 #430000

#제출 시각아이디문제언어결과실행 시간메모리
430000JasiekstrzVision Program (IOI19_vision)C++17
100 / 100
31 ms2044 KiB
#include<bits/stdc++.h> #include "vision.h" using namespace std; const int X=200; int h,w; vector<int> primes; bool composite[X+10]; int row[X+10]; // id of rows xor int col[X+10]; // id of columns xor vector<int> row_p[2]; vector<int> col_p[2]; int row_e[X+10]; int col_e[X+10]; int co(int x,int y) { return (x-1)*w+y-1; } void construct_network(int H,int W,int K) { vector<int> tmp; h=H;w=W; int it=h*w; int n=max(h,w); for(int i=2;i<=n;i++) { if(composite[i]) continue; for(int j=i;j<=n;j*=i) primes.push_back(j); for(int j=2*i;j<=n;j+=i) composite[j]=true; } sort(primes.begin(),primes.end()); // rows for(int i=1;i<=h;i++) { row[i]=it++; tmp.clear(); for(int j=1;j<=w;j++) tmp.push_back(co(i,j)); add_xor(tmp); } // columns for(int j=1;j<=w;j++) { col[j]=it++; tmp.clear(); for(int i=1;i<=h;i++) tmp.push_back(co(i,j)); add_xor(tmp); } // rows divisors for(auto p:primes) { if(p>h) break; vector<int> modt(p); for(int i=1;i<=p;i++) { if(i+p>h) modt[i-1]=row[i]; else { modt[i-1]=it++; tmp.clear(); for(int j=i;j<=h;j+=p) tmp.push_back(row[j]); add_xor(tmp); } } row_p[0].push_back(it++); add_or(modt); row_p[1].push_back(it++); add_not(row_p[0].back()); //cerr<<"row_p "<<p<<" {"<<row_p[1].back()<<","<<row_p[0].back()<<"}\n"; } // columns divisors for(auto p:primes) { if(p>w) break; vector<int> modt(p); for(int i=1;i<=p;i++) { if(i+p>w) modt[i-1]=col[i]; else { modt[i-1]=it++; tmp.clear(); for(int j=i;j<=w;j+=p) tmp.push_back(col[j]); add_xor(tmp); } } col_p[0].push_back(it++); add_or(modt); col_p[1].push_back(it++); add_not(col_p[0].back()); //cerr<<"col_p "<<p<<" {"<<col_p[1].back()<<","<<col_p[0].back()<<"}\n"; } // rows equal if(h==1) { row_e[0]=it++; add_not(row[1]); } else { for(int i=0;i<h;i++) { row_e[i]=it++; tmp.clear(); for(size_t j=0;j<row_p[1].size();j++) tmp.push_back(row_p[i%primes[j]==0][j]); add_and(tmp); //cerr<<"row_e "<<i<<" "<<row_e[i]<<"\n"; } } // columns equal if(w==1) { col_e[0]=it++; add_not(col[1]); } else { for(int i=0;i<w;i++) { col_e[i]=it++; tmp.clear(); for(size_t j=0;j<col_p[1].size();j++) tmp.push_back(col_p[i%primes[j]==0][j]); add_and(tmp); //cerr<<"col_e "<<i<<" "<<col_e[i]<<"\n"; } } // answer vector<int> ans; for(int r=0;r<=min(K,h-1);r++) { int c=K-r; if(c>w-1) continue; ans.push_back(it++); tmp={row_e[r],col_e[c]}; add_and(tmp); } add_or(ans); return; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...