Submission #1209742

#TimeUsernameProblemLanguageResultExecution timeMemory
1209742M_SH_ODEL13 (info1cup18_del13)C++20
0 / 100
3 ms580 KiB
#include <bits/stdc++.h> /*#include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp>*/ #define ll long long #define ll1 long long #define ull unsigned long long #define dou long double #define str string #define vll vector<ll> #define vi vector<int> #define pll pair<ll, ll> #define vpll vector<pll> #define vbool vector<bool> #define vstr vector<str> #define vvll vector<vll> #define pb push_back #define pf push_front #define endl "\n" #define fr first #define se second // #define sortcmp(a) sort(a.begin(), a.end(), cmp) #define sort(a) sort(a.begin(), a.end()) #define reverse(a) reverse(a.begin(), a.end()) #define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define INF 5000000000000000000 #define ordered_set tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> using namespace std; //using namespace __gnu_pbds; mt19937 rng(1488); ll randll(ll l, ll r){ return uniform_int_distribution<ll>(l, r)(rng); } int main() { speed; srand(time(0)); ll t; cin >> t; while (t --) { ll n, k; cin >> n >> k; vll a; a.pb(0); vll b1; for (int i = 0; i < k; i ++) { ll b; cin >> b; b1.pb(b); a.pb(b); } a.pb(n+1); vll b; for (int i = 1; i < a.size(); i ++) { b.pb(a[i]-a[i-1]-1); //cout << a[i]-a[i-1]-1 << ' '; } //cout << endl; vll res1; ll cnt = 0; for (int i = 0; i < b.size(); i ++) { if (b[i] % 2) cnt ++; else { if (cnt % 2 == 1) { ll x = -1; for (int j = i+1; j < b.size(); j ++) { if (b[j] % 2) { x = j; break; } } if (x != -1) { while (x > i) { res1.pb(a[x-1]); b[x] --; b[x-1] --; x --; } } } cnt = 0; } } vbool dp[2]; dp[0].resize(n, 0); dp[1].resize(n, 0); dp[0][0] = 1; if (b[0] == 0) { dp[0][0] = 0; dp[1][0] = 1; } for (int i = 1; i < b.size(); i ++) { if (b[i] == 0) { if (dp[1][i-1]) dp[1][i] = 1; //cout << dp[0][i] << ' ' << dp[1][i] << endl; continue; } if (dp[0][i-1]) { if (b[i-1] % 2 == 1 && b[i] % 2 == 1) { dp[1][i] = 1; } if (b[i-1] % 2 == 0) { if (b[i] % 2 == 1 && b[i] > 1) dp[0][i] = 1; if (b[i] % 2 == 0) dp[1][i] = 1; } } if (dp[1][i-1]){ dp[0][i] = 1; if (b[i] % 2 == 0 && b[i-1] > 2) dp[1][i] = 1; } //cout << dp[0][i] << ' ' << dp[1][i] << endl; } if (!dp[1][b.size()-1]) { //while (1); cout << -1 << endl; continue; } ll k1 = 1; vll res; vll c = b; for (int i = b.size()-1; i > 0; i --) { if (b[i] == 0) continue; if (dp[0][i-1]) { if (b[i-1] % 2 == 1 && b[i] % 2 == 1 && k1) { c[i] --; c[i-1] --; res.pb(a[i]); k1 = 0; continue; } if (b[i-1] % 2 == 0) { if (b[i] % 2 == 1 && b[i] > 1 && !k1) { c[i] -= 2; c[i-1] -= 2; res.pb(a[i]); res.pb(a[i]); continue; } if (b[i] % 2 == 0 && k1) { c[i] -= 2; c[i-1] -= 2; res.pb(a[i]); res.pb(a[i]); k1 = 0; continue; } } } if (dp[1][i-1]){ if (!k1) { k1 = 1; continue; } if (b[i] % 2 == 0 && b[i-1] > 2 && k1) { c[i] -= 2; c[i-1] -= 2; res.pb(a[i]); res.pb(a[i]); k1 = 1; } } } for (int i = 0; i < c.size(); i ++) { if (c[i] % 2) while (1); for (int j = 0; j < c[i]/2; j ++) { res.pb((a[i]+a[i+1])/2); } } reverse(res); /*vll d; for (int i = 1; i <= n; i ++) { d.pb(i); } bool q = 1; for (int i : res) { for (int j = 0; j < d.size(); j ++) { if (d[j] == i) { if (j == 0 || j == d.size()-1) { q = 0; break; } d.erase(d.begin()+j+1); d.erase(d.begin()+j-1); } } if (!q) break; } if (d != b1) q = 0; if (!q) { /*cout << "!!!!!!" << endl; cout << n << ' ' << k << endl; for (int i = 0; i < k; i ++) { cout << b1[i] << ' '; } cout << endl; return 0; while (1); }*/ cout << res.size()+res1.size() << endl; for (int i : res1) { cout << i << ' '; } for (int i : res) { cout << i << ' '; } cout << endl; } }
#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...