| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 399422 | proma | 벽 칠하기 (APIO20_paint) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
bool bin_search (vector <int> &V, int val) {
int l = 0, r = int(V.size()) - 1;
while (l <= r) {
int m = (l + r) / 2;
if (V[m] == val) return true;
if (V[m] < val) l = m + 1;
else r = m - 1;
}
return false;
}
bool subtask1 (int N, int M, int pos[], vector <int> &C, int P[]) {
int lft = 0;
if (pos[C[0]] == -1) return 1;
for (int y = 1; y < N; y ++) {
if (pos[C[y]] == -1) return 1;
if (pos[C[y]] != (pos[C[y-1]] + 1) % M) {
for (int i = lft; i <= y - M; i ++) {
P[i] = 1;
}
lft = y;
}
}
for (; lft <= N - M; lft ++)
P[lft] = 1;
return 0;
}
int minimumInstructions (int N, int M, int K, vector <int> C, vector <int> A, vector <vector<int>> B) {
int P[N], L[N], G[N+M], pos[K];
int subtask = 1;
memset(pos, -1, sizeof(pos));
for (int i = 0; i < M; i ++) {
for (int j = 0; j < A[i]; j ++) {
if (pos[B[i][j]] != -1) {
subtask = 0;
}
pos[B[i][j]] = i;
}
}
memset(P, 0, sizeof(P));
if (subtask and subtask1(N, M, pos, C, P)) {
return -1;
}
else {
for (int y = 0; y <= N - M; y ++) {
for (int x = 0; x < M; x ++) {
if (bin_search(B[x], C[y])) {
int flag = 0;
for (int l = 1; l < M; l ++) {
if (!bin_search(B[(x + l) % M], C[y + l])) {
flag = 1;
break;
}
}
if (!flag) {
P[y] = 1;
}
}
}
}
}
if (P[0]) L[0] = 0;
else return -1;
for (int i = 1; i < N; i ++) {
if (P[i]) L[i] = i;
else L[i] = L[i-1];
}
memset(G, 0, sizeof(G));
for (int i = N - 1; i >= 0; i --) {
if (i - L[i] >= M) {
return -1;
}
G[i] = 1 + G[L[i] + M];
}
return G[0];
}
void solve () {
int N, M, K;
vector <int> C, A;
vector <vector<int>> B;
cin >> N >> M >> K;
C.resize(N);
A.resize(M);
B.resize(M);
for (int i = 0; i < N; i ++) {
cin >> C[i];
}
for (int i = 0; i < M; i ++) {
cin >> A[i];
B[i].resize(A[i]);
for (int j = 0; j < A[i]; j ++) {
cin >> B[i][j];
}
}
cout << minimumInstructions(N, M, K, C, A, B) << endl;
}
int main () {
solve();
return 0;
}