Submission #1080312

#TimeUsernameProblemLanguageResultExecution timeMemory
1080312GrindMachineComparing Plants (IOI20_plants)C++17
11 / 100
4040 ms113520 KiB
#include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; #define pb push_back #define endl '\n' #define conts continue #define sz(a) (int)a.size() #define ff first #define ss second #define all(a) a.begin(),a.end() #define rall(a) a.rbegin(),a.rend() #define rep(i,n) for(int i = 0; i < n; ++i) #define rep1(i,n) for(int i = 1; i <= n; ++i) #define rev(i,s,e) for(int i = s; i >= e; ++i) #define trav(i,a) for(auto &i : a) template<typename T> void amin(T &x, T y){ x = min(x,y); } template<typename T> void amax(T &x, T y){ x = max(x,y); } template<typename A,typename B> string to_string(pair<A,B> p); string to_string(const string &s){ return "'"+s+"'"; } string to_string(const char* s){ return to_string((string)s); } string to_string(bool b){ return b?"true":"false"; } template<typename A> string to_string(A v){ string res = "{"; trav(x,v){ res += to_string(x)+","; } if(res.back() == ',') res.pop_back(); res += "}"; return res; } template<typename A,typename B> string to_string(pair<A,B> p){ return "("+to_string(p.ff)+","+to_string(p.ss)+")"; } #define debug(x) cout << "[" << #x << "]: "; cout << to_string(x) << endl const int MOD = 1e9 + 7; const int N = 1<<15; const int inf1 = 1e9 + 5; const ll inf2 = (ll)1e18 + 5; #include "plants.h" pii d_neutral = {inf1,-1}; vector<pii> tr(4*N,d_neutral); vector<int> lz(4*N); void propagate(int x, int lx, int rx){ int v = lz[x]; tr[x].ff += v; if(rx-lx > 1){ lz[x<<1] += v; lz[x<<1|1] += v; } lz[x] = 0; } void rupd(int x, int lx, int rx, int l, int r, int v){ propagate(x,lx,rx); if(lx >= r or rx <= l) return; if(lx >= l and rx <= r){ lz[x] = v; propagate(x,lx,rx); return; } int mid = (lx+rx)>>1; rupd(x<<1,lx,mid,l,r,v); rupd(x<<1|1,mid,rx,l,r,v); tr[x] = min(tr[x<<1],tr[x<<1|1]); } void rupd(int l, int r, int v){ rupd(1,0,N,l,r+1,v); } pii query(){ propagate(1,0,N); return tr[1]; } void build(int x, int lx, int rx, vector<int> &a){ if(rx-lx == 1){ if(lx < sz(a)){ tr[x] = {a[lx],lx}; } return; } int mid = (lx+rx) >> 1; build(x<<1,lx,mid,a); build(x<<1|1,mid,rx,a); tr[x] = min(tr[x<<1],tr[x<<1|1]); } void build(vector<int> &a){ build(1,0,N,a); } vector<int> id(N); vector<int> adj[N]; bool reach[N][N]; void dfs(int u, int s){ reach[s][u] = 1; trav(v,adj[u]){ if(reach[s][v]) conts; dfs(v,s); } } void init(int k, std::vector<int> a) { k--; int n = sz(a); build(a); int iter = 0; int rem_cnt = 0; vector<bool> remm(n); auto rem = [&](int i){ remm[i] = 1; rem_cnt++; id[i] = iter; if(i-k >= 0){ rupd(i-k,i-1,-1); } else{ rupd(0,i-1,-1); rupd(i-k+n,n-1,-1); } // int j = i; // rep1(x,k){ // j = (j+1)%n; // if(!remm[j]){ // adj[i].pb(j); // } // else{ // adj[j].pb(i); // } // } }; set<int> zeros; set<pii> dis; while(rem_cnt < n){ iter++; while(true){ auto [mn,i] = query(); if(mn == 0){ rupd(i,i,inf1); zeros.insert(i); auto it = zeros.find(i); int prevv = -1, nxt = -1; if(it != zeros.begin()){ prevv = *prev(it); } if(next(it) != zeros.end()){ nxt = *next(it); } if(prevv != -1 and nxt != -1) dis.erase({nxt-prevv,nxt}); if(prevv != -1) dis.insert({i-prevv,i}); if(nxt != -1) dis.insert({nxt-i,nxt}); } else{ break; } } if(sz(zeros) == 1){ trav(i,zeros){ rem(i); } zeros.clear(); dis.clear(); conts; } vector<int> del; { int i = *zeros.begin(), j = *zeros.rbegin(); int d = (i-j+n)%n; if(d > k){ del.pb(i); } } for(auto it = dis.rbegin(); it != dis.rend(); ++it){ auto [d,i] = *it; if(d > k){ del.pb(i); } else{ break; } } trav(i,del){ rem(i); auto it = zeros.find(i); int prevv = -1, nxt = -1; if(it != zeros.begin()){ prevv = *prev(it); } if(next(it) != zeros.end()){ nxt = *next(it); } zeros.erase(it); if(prevv != -1) dis.erase({i-prevv,i}); if(nxt != -1) dis.erase({nxt-i,nxt}); if(prevv != -1 and nxt != -1) dis.insert({nxt-prevv,nxt}); } } rep(i,n){ int j = i; rep1(x,k){ j = (j+1)%n; if(id[i] < id[j]){ adj[i].pb(j); } else{ adj[j].pb(i); } } } rep(i,n){ dfs(i,i); } } int compare_plants(int x, int y) { if(reach[x][y]) return 1; if(reach[y][x]) return -1; return 0; if(id[x] < id[y]) return 1; if(id[x] > id[y]) return -1; return 0; }
#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...