# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
697501 | sharaelong | Painting Walls (APIO20_paint) | C++17 | 1600 ms | 266796 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>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5 + 1;
int minimumInstructions(int n, int m, int k, vector<int> C, vector<int> A, vector<vector<int>> B) {
vector<vector<int>> likes(k);
for (int i=0; i<m; ++i) {
for (int j=0; j<A[i]; ++j) {
likes[B[i][j]].push_back(i);
}
}
// for (int i=0; i<k; ++i) {
// for (int x: likes[i]) cout << x << ' ';
// cout << endl;
// }
vector<vector<int>> nxt(n);
vector<vector<bool>> processed(n);
for (int i=0; i<n; ++i) {
nxt[i].resize(likes[C[i]].size(), -1);
processed[i].resize(likes[C[i]].size(), false);
}
vector<int> pnt(n, 0);
for (int i=0; i+1<n; ++i) {
const vector<int>& cands = likes[C[i+1]];
for (int j=0; j<likes[C[i]].size(); ++j) {
int x = likes[C[i]][j];
if (x+1 < m) {
while (pnt[i+1] < cands.size() && cands[pnt[i+1]] <= x) pnt[i+1]++;
if (pnt[i+1] < cands.size() && cands[pnt[i+1]] == x+1) nxt[i][j] = pnt[i+1];
} else {
if (!cands.empty() && cands[0] == 0) nxt[i][j] = 0;
}
}
}
// for (int i=0; i<n; ++i) {
// for (int x: nxt[i]) cout << x << ' ';
// cout << endl;
// }
vector<int> okay(n+1, 0);
for (int i=0; i<n; ++i) {
for (int j=0; j<likes[C[i]].size(); ++j) {
if (!processed[i][j]) {
processed[i][j] = true;
int ii = i, jj = j;
while (ii < n && nxt[ii][jj] != -1) {
jj = nxt[ii][jj];
ii++;
processed[ii][jj] = true;
}
if (ii == n) ii--;
if (ii-i+1 >= m) {
okay[i]++;
okay[ii-m+2]--;
}
}
}
}
for (int i=1; i<okay.size(); ++i) okay[i] += okay[i-1];
// for (int i=0; i<n; ++i) cout << okay[i] << ' ';
// cout << endl;
vector<int> valid_pos;
for (int i=0; i<n; ++i) {
if (okay[i] > 0) valid_pos.push_back(i);
}
if (valid_pos.empty() || valid_pos[0] > 0) return -1;
int ans = 1;
int curr = 0;
while (curr + m < n) {
auto it = upper_bound(valid_pos.begin(), valid_pos.end(), curr+m);
if (*prev(it) == curr) return -1;
curr = *prev(it);
ans++;
}
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... |