이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "paint.h"
#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define ROF(i,a,b) for(int i=(a); i>=(b); --i)
#define pb push_back
#define eb emplace_back
#define SZ(a) (int)(a).size()
#define all(a) (a).begin(), (a).end()
#define make_unique(a) sort(all((a))), (a).erase(unique(all((a))),(a).end())
#define x first
#define y second
#define MP make_pair
#define MT make_tuple
#define debug(x) cout << #x << " = " << x << endl
#define debug2(x,y) FOR(i,1,y) cout << "##"; cout << #x << " = " << x << endl
using namespace std;
typedef long long i64;
typedef tuple<int,int,int> iii;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long double ld;
int minimumInstructions(
int N, int M, int K, vector<int> C,
vector<int> A, vector<vector<int>> B) {
FOR(i, 0, M-1) sort(all(B[i]));
vi bef(M), aft(M);
vector<vi> color(K);
FOR(i, 0, M-1){
bef[i] = (i-1+M)%M;
aft[i] = (i+1)%M;
for(const int c : B[i]){
color[c].eb(i);
}
}
vi last(M,0);
vi good;
FOR(i, 0, N-1){
int mx = 1;
vector<pii> wait;
for(const int c : color[C[i]]){
wait.eb(c, 1);
if(last[bef[c]] == -1) continue;
mx = max(last[bef[c]]+1,mx);
wait.back().y = last[bef[c]]+1;
}
if(i==0){
FOR(j,0,M-1) last[j] = -1;
}else{
for(const int c : color[C[i-1]]){
last[c] = -1;
}
}
for(const pii e : wait){
last[e.x] = e.y;
}
if(mx >= M) good.eb(i);
}
if(good.empty()) return -1;
deque<pair<int,int>> q;
q.eb(-1, 0);
for(const int e : good){
while(!q.empty() && q.front().x < e-M) q.pop_front();
if(q.empty()){
return -1; // impossible
}
q.eb(e, q.front().y+1);
}
return q.back().y;
}
/*
8 3 5
3 3 1 3 4 4 2 2
3 0 1 2
2 2 3
2 3 4
5 4 4
1 0 1 2 2
2 0 1
1 1
1 2
1 3
*/
# | 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... |