Submission #47168

#TimeUsernameProblemLanguageResultExecution timeMemory
47168KmcodeDEL13 (info1cup18_del13)C++14
100 / 100
29 ms1704 KiB
#include "bits/stdc++.h" using namespace std; #define MAX 100002 int n; vector<int> v; int q; vector<pair<int, int> > vv; bool ng; vector<int> ope; vector<int> v2; bool dp[MAX][5]; int pr[MAX][5]; int rest[MAX][5]; void er() { v2.clear(); for (int i = 0; i < vv.size(); i++) { v2.push_back(vv[i].second - vv[i].first + 1); } for (int i = 0; i <= v2.size(); i++) { for (int j = 0; j < 5; j++) { dp[i][j] = false; } } dp[0][0] = true; pr[0][0] = 0; for (int i = 0; i < v2.size(); i++) { vector<int> tmp; int num = v2[i]; while (num > 2) { tmp.push_back(num); num -= 2; } tmp.push_back(num); reverse(tmp.begin(), tmp.end()); int lim = min(5, (int)tmp.size()); for (int j = 0; j < 5; j++) { for (int k = 0; k < lim; k++) { int lef = j; if (dp[i][j] == false)continue; int rig = tmp[k]; if (lef > rig)continue; rig -= lef; if (rig < 5) { rest[i + 1][rig] = tmp[k]; dp[i + 1][rig] = true; pr[i + 1][rig] = j; } } } } ng |= (dp[v2.size()][0] ^ true); if (ng == false) { int cur = 0; vector<int> tmp; for (int i = v2.size() - 1; i >= 0; i--) { { int z = pr[i+1][cur]; while (z--) { tmp.push_back(vv[i].first - 1); } } vector<int> ar; for (int i2 = vv[i].first; i2 <= vv[i].second; i2++) { ar.push_back(i2); } while (ar.size() > rest[i+1][cur]) { int a = ar.back(); ar.pop_back(); int b = ar.back(); ar.pop_back(); int c = ar.back(); ar.pop_back(); tmp.push_back(b); ar.push_back(b); } cur = pr[i+1][cur]; } reverse(tmp.begin(), tmp.end()); for (int el : tmp) { ope.push_back(el); } } vv.clear(); return; } int main() { int t; cin >> t; while (t--) { ope.clear(); ng = false; scanf("%d%d", &n,&q); v.clear(); v.push_back(0); for (int i = 0; i < q; i++) { int a; scanf("%d", &a); v.push_back(a); } v.push_back(n+1); v.push_back(n + 2); for (int i = 1; i < v.size(); i++) { if (v[i] - v[i - 1] - 1 == 0) { er(); continue; } vv.push_back(make_pair(v[i - 1] + 1, v[i] - 1)); } if (ng) { puts("-1"); } else { cout << ope.size() << endl; bool out = false; for (int el : ope) { if (out) { printf(" "); } out = true; printf("%d", el); } puts(""); } } return 0; }

Compilation message (stderr)

del13.cpp: In function 'void er()':
del13.cpp:25:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vv.size(); i++) {
                  ~~^~~~~~~~~~~
del13.cpp:28:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i <= v2.size(); i++) {
                  ~~^~~~~~~~~~~~
del13.cpp:35:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v2.size(); i++) {
                  ~~^~~~~~~~~~~
del13.cpp:75:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while (ar.size() > rest[i+1][cur]) {
           ~~~~~~~~~~^~~~~~~~~~~~~~~~
del13.cpp:76:9: warning: unused variable 'a' [-Wunused-variable]
     int a = ar.back();
         ^
del13.cpp:80:9: warning: unused variable 'c' [-Wunused-variable]
     int c = ar.back();
         ^
del13.cpp: In function 'int main()':
del13.cpp:112:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 1; i < v.size(); i++) {
                   ~~^~~~~~~~~~
del13.cpp:102:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &n,&q);
   ~~~~~^~~~~~~~~~~~~~~
del13.cpp:107:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &a);
    ~~~~~^~~~~~~~~~
#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...