Submission #1190286

#TimeUsernameProblemLanguageResultExecution timeMemory
1190286Zbyszek99Vision Program (IOI19_vision)C++20
100 / 100
18 ms2880 KiB
#include "vision.h" #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define ll long long #define ld long double #define ull unsigned long long #define ff first #define ss second #define pii pair<int,int> #define pll pair<long long, long long> #define vi vector<int> #define vl vector<long long> #define pb push_back #define rep(i, b) for(int i = 0; i < (b); ++i) #define rep2(i,a,b) for(int i = a; i <= (b); ++i) #define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c) #define count_bits(x) __builtin_popcountll((x)) #define all(x) (x).begin(),(x).end() #define siz(x) (int)(x).size() #define forall(it,x) for(auto& it:(x)) using namespace __gnu_pbds; using namespace std; typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; //mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());} //ll los(ll a, ll b) {return a + (mt() % (b-a+1));} const int INF = 1e9+50; const ll INF_L = 1e18+40; const ll MOD = 1e9+7; int H,W,K; int col_or[200]; int row_or[200]; int xbit_ans[200]; int notxbit_ans[200]; int ybit_ans[200]; int notybit_ans[200]; int distx[200]; int disty[200]; int bitx = 0; int bity = 0; int cell(int y, int x) { return W*y + x; } void get_x_bit(int bit) { vi used; rep(i,W) { vi match; rep2(j,i+1,W-1) { if((j-i) & (1 << bit)) { match.pb(col_or[j]); } } if(siz(match) == 0) continue; int or_ = add_or(match); used.pb(add_and({or_,col_or[i]})); } if(siz(used) == 0) return; xbit_ans[bit] = add_or(used); notxbit_ans[bit] = add_not(xbit_ans[bit]); } void get_y_bit(int bit) { vi used; rep(i,H) { vi match; rep2(j,i+1,H-1) { if((j-i) & (1 << bit)) { match.pb(row_or[j]); } } if(siz(match) == 0) continue; int or_ = add_or(match); used.pb(add_and({or_,row_or[i]})); } if(siz(used) == 0) return; ybit_ans[bit] = add_or(used); notybit_ans[bit] = add_not(ybit_ans[bit]); } void get_x_dist(int d) { vi used; rep(bit,bitx+1) { if(d & (1 << bit)) { used.pb(xbit_ans[bit]); } else { used.pb(notxbit_ans[bit]); } } if(siz(used) == 0) return; distx[d] = add_and(used); } void get_y_dist(int d) { vi used; rep(bit,bity+1) { if(d & (1 << bit)) { used.pb(ybit_ans[bit]); } else { used.pb(notybit_ans[bit]); } } if(siz(used) == 0) return; disty[d] = add_and(used); } void construct_network(int h, int w, int k) { H = h; W = w; K = k; if(W != 0) { bitx = __lg(W-1); } else bitx = -1; if(H != 0) { bity = __lg(H-1); } else bity = -1; //cor_or rep(i,W) { vi used; rep(j,H) used.pb(cell(j,i)); col_or[i] = add_or(used); } //row_or rep(i,H) { vi used; rep(j,W) used.pb(cell(i,j)); row_or[i] = add_or(used); } rep(b,bitx+1) get_x_bit(b); rep(b,bity+1) get_y_bit(b); rep(i,W) get_x_dist(i); rep(i,H) get_y_dist(i); vi used; rep(i,W) { if(i > k) continue; if(W == 1) { if(K-i >= 0 && K-i < H) { used.pb(add_and({disty[K-i]})); } } else if(H == 1) { if(i == K) { used.pb(add_and({distx[i]})); } } else { if(K-i >= 0 && K-i < H) { used.pb(add_and({distx[i],disty[K-i]})); } } } if(siz(used) > 0) { add_or(used); } else { vi all_; rep(i,H*W) all_.pb(i); int xd = add_or(all_); add_not({xd}); } }
#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...