Submission #127474

#TimeUsernameProblemLanguageResultExecution timeMemory
127474E869120DEL13 (info1cup18_del13)C++14
100 / 100
54 ms17812 KiB
#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 (stderr)

del13.cpp:5:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
del13.cpp: In function 'std::vector<int> solve(int, std::vector<int>)':
del13.cpp:25:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i <= A.size(); i++) vec[A[i - 1]].push_back(i);
                  ~~^~~~~~~~~~~
del13.cpp:26:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i <= A.size() - 1; i++) {
                  ~~^~~~~~~~~~~~~~~
del13.cpp:36:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < vec[i].size(); j++) {
                   ~~^~~~~~~~~~~~~~~
del13.cpp:39:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int k = 0; k < vec[i - 1].size(); k++) {
                    ~~^~~~~~~~~~~~~~~~~~~
del13.cpp:96:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i <= A.size(); i++) {
                  ~~^~~~~~~~~~~
del13.cpp: In function 'int main()':
del13.cpp:127:27: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
    printf("%d\n", L.size());
                   ~~~~~~~~^
del13.cpp:128:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < L.size(); j++) { if (j) printf(" "); printf("%d", L[j]); }
                    ~~^~~~~~~~~~
del13.cpp:118:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int T; scanf("%d", &T);
         ~~~~~^~~~~~~~~~
del13.cpp:121:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &N1, &V1);
   ~~~~~^~~~~~~~~~~~~~~~~~
del13.cpp:122:47: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for (int j = 1; j <= V1; j++) { int p; scanf("%d", &p); A1.push_back(p); }
                                          ~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...