# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
550773 | Jarif_Rahman | Painting Walls (APIO20_paint) | C++17 | 802 ms | 252692 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 pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
int minimumInstructions(int n, int m, int K, vector<int> C, vector<int> A, vector<vector<int>> B){
vector<vector<int>> liked_by(K);
vector<vector<pair<int, int>>> next(K);
vector<vector<int>> sth(n);
for(int i = 0; i < m; i++) for(int x: B[i])
next[x].pb({(i+1)%m, liked_by[x].size()}), liked_by[x].pb(i);
for(int i = 0; i < K; i++) sort(next[i].begin(), next[i].end());
for(int i = 0; i < n; i++) sth[i] = vector<int>(liked_by[C[i]].size(), 1);
vector<bool> p(n, 0);
for(int i = n-2; i >= 0; i--){
int a = 0, b = 0;
while(a < next[C[i]].size() && b < liked_by[C[i+1]].size()){
if(next[C[i]][a].f == liked_by[C[i+1]][b])
sth[i][next[C[i]][a].sc] = sth[i+1][b]+1, a++, b++;
else if(next[C[i]][a].f < liked_by[C[i+1]][b]) a++;
else b++;
}
}
for(int i = 0; i < n; i++) for(int x: sth[i]) if(x >= m) p[i] = 1;
int ans = 0, ls = -1, c = 0;
for(int i = n-1; i >= 0; i--){
c++;
if(p[i]) ls = i;
if(c == m || i == 0){
if(ls == -1) return -1;
ans++;
c=ls-i;
ls = -1;
}
}
return ans;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |