Submission #1233801

#TimeUsernameProblemLanguageResultExecution timeMemory
1233801thelegendary08Painting Walls (APIO20_paint)C++17
0 / 100
0 ms328 KiB
#include "paint.h" #include<bits/stdc++.h> #define int long long #define mp make_pair #define pb push_back #define f0r(i,n) for(signed i = 0; i<n; i++) #define FOR(i, k, n) for(signed i = k; i<n; i++) #define vi vector<int> #define vpii vector<pair<int,int>> #define pii pair<int,int> #define vb vector<bool> #define mii map<int,int> #define vvi vector<vector<int>> #define vout(v) for(auto u : v)cout<<u<<' '; cout<<endl; #define dout(a) cout<<a<<' '<<#a<<endl; #define dout2(a,b) cout<<a<<' '<<#a<<' '<<b<<' '<<#b<<endl; using namespace std; signed minimumInstructions( signed n, signed m, signed k, std::vector<signed> c, std::vector<signed> a, std::vector<std::vector<signed>> b) { map<pii, int>state; vpii w; vb can(n); vector<set<int>> f(k); f0r(i,m){ f0r(j, a[i]){ f[b[i][j]].insert(i); // state[mp(i, b[i][j])] = -1; // w.pb(mp(i, b[i][j])); } } /* f0r(i,n){ for(auto u : f[c[i]]){ state[mp(i, u)] = -1; w.pb(mp(i,u)); } } sort(w.begin(), w.end()); */ vvi q(m, vi(2, -4e18)); for(auto u : f[c[n-1]]){ q[u][0] = n-1; } int md = 1; for(int i = n-2; i>=0; i--){ for(auto u : f[c[i]]){ if(q[(u + 1) % m][1 - md] == -4e18){ q[u][md] = i; } else{ q[u][md] = q[(u + 1) % m][1 - md]; } } for(auto u : f[c[i+1]]){ q[u][1 - md] = -4e18; } for(auto u : f[c[i]]){ if(q[u][md] >= i + m - 1)can[i] = 1; } md = 1-md; } // vout(can); // cout<<endl; vi cans; f0r(i, n){ if(can[i])cans.pb(i); } if(!can[0])return -1; if(cans.back() != n - m)return -1; int cur = 0; int cnt = 1; int ep = n - m; while(cur < ep){ cnt++; int lo = 0; int hi = cans.size() - 1; //last one less than or equal to cur + m while(lo < hi){ int mid = lo + (hi - lo + 1) / 2; if(cans[mid] <= cur + m){ lo = mid; } else{ hi = mid - 1; } } if(cans[lo] == cur)return -1; cur = cans[lo]; } return cnt; }
#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...