제출 #1077415

#제출 시각아이디문제언어결과실행 시간메모리
1077415GrindMachine벽 칠하기 (APIO20_paint)C++17
51 / 100
1549 ms161612 KiB
#include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL) #define pb push_back #define endl '\n' #define conts continue #define sz(a) (int)a.size() #define all(a) a.begin(),a.end() #define rall(a) a.rbegin(),a.rend() #define ff first #define ss second #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"; } string to_string(vector<bool> v){ string res = "{"; rep(i,sz(v)){ res += to_string(v[i])+","; } if(res.back() == ',') res.pop_back(); res += "}"; return res; } 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 = 1e5 + 5; const int inf1 = 1e9 + 5; const ll inf2 = (ll)1e18 + 5; #include "paint.h" int minimumInstructions( int n, int m, int k, std::vector<int> a, std::vector<int> sizes, std::vector<std::vector<int>> b) { vector<int> here[k]; rep(j,m){ trav(x,b[j]){ here[x].pb(j); } } vector<int> enter[n], leave[n]; rep(i,n){ trav(j,here[a[i]]){ int shift = min(i,m-1); int x = (j-shift+m)%m; enter[i-shift].pb(x); leave[i].pb(j); } } int ref = 0; vector<int> val(m); auto rot = [&](){ if(ref == 0) ref = m-1; else ref--; // debug(ref); // debug(val); // cout << endl; // rotate(val.begin(),val.begin()+m-1,val.end()); // debug(val); // cout << endl; }; auto upd = [&](int x, int v){ x = (x+ref)%m; val[x] += v; }; vector<bool> can(n); rep(i,n){ if(i+m-1 >= n) break; if(i) rot(); trav(x,enter[i]){ upd(x,1); } int mx = *max_element(all(val)); assert(mx <= m); if(mx == m){ can[i] = 1; } trav(x,leave[i]){ upd(x,-1); } } // rep(i,n){ // if(i+m-1 >= n) break; // rep(x,m){ // bool ok = true; // rep(l,m){ // int j = (x+l)%m; // if(!binary_search(all(b[j]),a[i+l])){ // ok = false; // break; // } // } // if(ok){ // can[i] = 1; // break; // } // } // } vector<int> bef(n,-1); rep(i,n){ if(i) bef[i] = bef[i-1]; if(can[i]) bef[i] = i; } if(!can[0]){ return -1; } int pos = 0; int ans = 1; while(pos+m < n){ int nxt = bef[pos+m]; if(nxt == pos) return -1; pos = nxt; ans++; } return ans; }
#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...