제출 #127357

#제출 시각아이디문제언어결과실행 시간메모리
127357E869120DEL13 (info1cup18_del13)C++14
15 / 100
19 ms2220 KiB
#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) 메시지

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:18:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < A.size(); i++) {
                  ~~^~~~~~~~~~
del13.cpp:64: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:96: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:86: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:89: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:90: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...