# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
289372 | beso123 | Painting Walls (APIO20_paint) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "paint.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
int minimumInstructions(int n,int m,int s,vector<int> col,vector<int> Size,vector<vector<int>> b){
vector<int> mp[s+1];
for(int k=0;k<m;k++){
for(int i=0;i<Size[k];i++){
mp[b[k][i]].push_back(k);
}
}
deque<int> v;
v.resize(m,0);
for(int k=0;k<m;k++){
for(int i=0;i<mp[col[k]].size();i++){
int nom=mp[col[k]][i];
nom=((nom-k)+m)%m;
v[nom]++;
}
}
vector<int> a(n,0);
for(int k=0;k<v.size();k++)
if(v[k]==m)
a[m-1]++;
for(int k=m;k<n;k++){
int cl=col[k-m];
for(int i=0;i<mp[cl].size();i++){
v[mp[cl][i]]--;
}
cl=col[k];
int x=v[v.size()-1];
v.pop_back();
v.push_front(x);
for(int i=0;i<mp[cl].size();i++){
v[(mp[cl][i]+1)%m]++;
if(v[(mp[cl][i]+1)%m]==m)
a[k]++;
}
}
int ans=0;
vector<int> w(n+1,-1);
if(a[m-1]==1)
w[m-1]=m-1;
for(int k=m;k<n;k++){
w[k]=w[k-1];
if(a[k]==1)
w[k]=k;
}
int j=m-1;
while(true){
if(w[j]==-1)
return -1;
ans++;
if(j==n-1)
break;
int i=(j+m);
if(i>=n)
i=n-1;
if(w[i]==w[j])
return -1;
j=w[i];
}
return ans;
}