| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 127474 | 2019-07-09T12:02:01 Z | E869120 | DEL13 (info1cup18_del13) | C++14 | 54 ms | 17812 KB |
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#pragma warning (disable: 4996)
int col[1 << 17], cl[1 << 17], cr[1 << 17]; vector<int> vec[1 << 17];
// (pos, 現在の値, 左端が A[i] か, 区間の長さの偶奇)
int dp[1 << 17][2][4]; pair<int, int> pres[1 << 17][2][4];
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); vec[i].clear();
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 4; k++) { dp[i][j][k] = 0; pres[i][j][k] = make_pair(-1, -1); }
}
}
// 前処理
for (int i = 1; i <= A.size(); i++) vec[A[i - 1]].push_back(i);
for (int i = 1; i <= A.size() - 1; i++) {
for (int j = A[i - 1] + 1; j <= A[i] - 1; j++) { vec[j].push_back(i); vec[j].push_back(i + 1); }
}
for (int i = 1; i < A[0]; i++) { vec[i].push_back(0); vec[i].push_back(1); }
for (int i = A[A.size() - 1] + 1; i <= N; i++) { vec[i].push_back(A.size()); vec[i].push_back(A.size() + 1); }
vec[0].push_back(0);
// 計算
dp[0][0][3] = 1;
for (int i = 1; i <= N; i++) {
for (int j = 0; j < vec[i].size(); j++) {
// dp[i][j] に向けての遷移
for (int k = 0; k < vec[i - 1].size(); k++) {
// パターン A : 小さくなるパターン
if (vec[i - 1][k] > vec[i][j]) continue;
// パターン B : 変化しないパターン
if (vec[i - 1][k] == vec[i][j]) {
if (dp[i - 1][k][0] == 1) { dp[i][j][2] = 1; pres[i][j][2] = make_pair(k, 0); }
if (dp[i - 1][k][1] == 1) { dp[i][j][3] = 1; pres[i][j][3] = make_pair(k, 1); }
if (dp[i - 1][k][2] == 1) { dp[i][j][0] = 1; pres[i][j][0] = make_pair(k, 2); }
if (dp[i - 1][k][3] == 1) { dp[i][j][1] = 1; pres[i][j][1] = make_pair(k, 3); }
}
// パターン C : 変化し大きくなるパターン
if (vec[i - 1][k] < vec[i][j]) {
if (vec[i - 1].size() == 1 && vec[i].size() == 1) {
// C-1 : 長さは 1 でなければならない、かつ今回も長さ 1 制限あり
if (dp[i - 1][k][3] == 1) { dp[i][j][3] = 1; pres[i][j][3] = make_pair(k, 3); }
}
if (vec[i - 1].size() == 1 && vec[i].size() != 1) {
// C-2 : 長さは 1 でなければならない、かつ今回も長さ 1 制限なし
if (dp[i - 1][k][3] == 1) { dp[i][j][2] = 1; pres[i][j][2] = make_pair(k, 3); }
}
if (vec[i - 1].size() != 1 && vec[i].size() == 1) {
// C-3 : 長さは 1 であってはならない、かつ今回も長さ 1 制限あり
if (dp[i - 1][k][2] == 1) { dp[i][j][3] = 1; pres[i][j][3] = make_pair(k, 2); }
}
if (vec[i - 1].size() != 1 && vec[i].size() != 1) {
// C-4 : 長さは 1 であってはならない、かつ今回も長さ 1 制限なし
if (dp[i - 1][k][2] == 1) { dp[i][j][2] = 1; pres[i][j][2] = make_pair(k, 2); }
}
}
}
}
}
pair<int, int> cy = make_pair(-1, -1);
if (vec[N].size() == 1) {
if (dp[N][0][3] == 1) { cy = make_pair(0, 3); }
}
else {
if (dp[N][0][2] == 1) { cy = make_pair(0, 2); }
}
if (cy == make_pair(-1, -1)) return vector<int>{-1};
for (int i = N; i >= 1; i--) {
col[i] = vec[i][cy.first];
cy = pres[i][cy.first][cy.second];
}
// 答えを最後に求める
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", L.size());
for (int j = 0; j < L.size(); j++) { if (j) printf(" "); printf("%d", L[j]); }
printf("\n");
}
}
return 0;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 5 ms | 3448 KB | Output is correct |
| 2 | Correct | 5 ms | 3448 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 5 ms | 3448 KB | Output is correct |
| 2 | Correct | 5 ms | 3448 KB | Output is correct |
| 3 | Correct | 13 ms | 3448 KB | Output is correct |
| 4 | Correct | 14 ms | 3576 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 19 ms | 4220 KB | Output is correct |
| 2 | Correct | 6 ms | 3548 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 5 ms | 3448 KB | Output is correct |
| 2 | Correct | 5 ms | 3448 KB | Output is correct |
| 3 | Correct | 13 ms | 3448 KB | Output is correct |
| 4 | Correct | 14 ms | 3576 KB | Output is correct |
| 5 | Correct | 6 ms | 3448 KB | Output is correct |
| 6 | Correct | 6 ms | 3448 KB | Output is correct |
| 7 | Correct | 6 ms | 3448 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 5 ms | 3448 KB | Output is correct |
| 2 | Correct | 5 ms | 3448 KB | Output is correct |
| 3 | Correct | 13 ms | 3448 KB | Output is correct |
| 4 | Correct | 14 ms | 3576 KB | Output is correct |
| 5 | Correct | 6 ms | 3448 KB | Output is correct |
| 6 | Correct | 6 ms | 3448 KB | Output is correct |
| 7 | Correct | 6 ms | 3448 KB | Output is correct |
| 8 | Correct | 22 ms | 5240 KB | Output is correct |
| 9 | Correct | 24 ms | 6776 KB | Output is correct |
| 10 | Correct | 28 ms | 9852 KB | Output is correct |
| 11 | Correct | 54 ms | 17812 KB | Output is correct |