# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
127357 | E869120 | DEL13 (info1cup18_del13) | C++14 | 19 ms | 2220 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#pragma warning (disable: 4996)
bool forced[1 << 18];
int col[1 << 18], cl[1 << 18], cr[1 << 18];
vector<int> solve(int N, vector<int>A) {
if ((N - (int)A.size()) % 2 == 1) return vector<int>{-1};
if (A.size() == 0) return vector<int>{-1};
for (int i = 0; i <= N + 1; i++) {
col[i] = -1; cl[i] = (1 << 30); cr[i] = -(1 << 30); forced[i] = false;
}
for (int i = 0; i < A.size(); i++) {
if ((i + 1) % 2 == A[i] % 2) {
if (col[A[i]] >= 0) return vector<int>{-1};
else col[A[i]] = i + 1;
}
else {
if (col[A[i] - 1] >= 0 || col[A[i]] >= 0) return vector<int>{-1};
else { col[A[i] - 1] = i + 1; col[A[i]] = i + 1; col[A[i] + 1] = i + 1; }
}
}
for (int i = 1; i <= N - 1; i++) {
if (col[i] == -1 || col[i + 1] == -1) continue;
if (col[i] != col[i + 1]) {
if (col[i] % 2 == A[col[i] - 1] % 2) forced[col[i]] = true;
if (col[i + 1] % 2 == A[col[i + 1] - 1] % 2) forced[col[i + 1]] = true;
}
}
if (A[0] == 1) forced[1] = true;
if (A[A.size() - 1] == N) forced[A.size()] = true;
for (int i = 1; i <= N; i++) {
if (col[i] == -1) continue;
cl[col[i]] = min(cl[col[i]], i);
cr[col[i]] = max(cr[col[i]], i);
}
for (int i = 1; i < cl[1]; i++) col[i] = 1;
for (int i = cr[A.size()] + 1; i <= N; i++) col[i] = A.size();
for (int i = 1; i <= (int)A.size() - 1; i++) {
int el = cr[i] + 1, er = cl[i + 1] - 1;
if (forced[i] == true) { for (int j = el; j <= er; j++) col[j] = i + 1; }
else if (forced[i + 1] == true) { for (int j = el; j <= er; j++) col[j] = i; }
else {
for (int j = el; j <= (el + er) / 2; j++) col[j] = i;
for (int j = (el + er) / 2 + 1; j <= er; j++) col[j] = i + 1;
}
}
for (int i = 1; i <= N; i++) {
cl[col[i]] = min(cl[col[i]], i);
cr[col[i]] = max(cr[col[i]], i);
}
vector<int>ans;
for (int i = 1; i <= A.size(); i++) {
if (cl[i] == cr[i]) continue;
int lefthand = A[i - 1] - cl[i], righthand = cr[i] - A[i - 1];
if (lefthand == 0 || righthand == 0) return vector<int>{-1};
if ((cr[i] - cl[i]) % 2 == 1) return vector<int>{-1};
if (lefthand <= righthand) {
int mid = cr[i] - (righthand - lefthand) / 2;
for (int j = 0; j < (righthand - lefthand) / 2; j++) ans.push_back(mid);
for (int j = 0; j < lefthand; j++) ans.push_back(A[i - 1]);
}
if (lefthand > righthand) {
int mid = cl[i] + (lefthand - righthand) / 2;
for (int j = 0; j < (lefthand - righthand) / 2; j++) ans.push_back(mid);
for (int j = 0; j < righthand; j++) ans.push_back(A[i - 1]);
}
}
return ans;
}
int main() {
int T; scanf("%d", &T);
for (int i = 1; i <= T; i++) {
int N1, V1; vector<int>A1;
scanf("%d%d", &N1, &V1);
for (int j = 1; j <= V1; j++) { int p; scanf("%d", &p); A1.push_back(p); }
vector<int>L = solve(N1, A1);
if (L == vector<int>{-1}) printf("-1\n");
else {
printf("%d\n", (int)L.size());
for (int j = 0; j < L.size(); j++) { if (j) printf(" "); printf("%d", L[j]); }
printf("\n");
}
}
return 0;
}
컴파일 시 표준 에러 (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... |