Submission #1056417

#TimeUsernameProblemLanguageResultExecution timeMemory
1056417underwaterkillerwhaleRestore Array (RMI19_restore)C++17
45 / 100
23 ms1228 KiB
#include <bits/stdc++.h> #define ll long long #define rep(i,m,n) for(int i=(m); i<=(n); i++) #define reb(i,m,n) for(int i=(m); i>=(n); i--) #define pii pair<int,int> #define pll pair<ll,ll> #define MP make_pair #define fs first #define se second #define bit(msk, i) ((msk >> i) & 1) #define iter(id, v) for(auto id : v) #define pb push_back #define SZ(v) (int)v.size() #define ALL(v) v.begin(),v.end() using namespace std; mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count()); ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); } const int N = 1e4 + 7; const int Mod = 1e9 + 7; const int INF = 1e9 + 7; const ll BASE = 137; const int szBL = 320; struct Query { int l, r, k, val; }; int n, Q; int a[N]; Query qr[N]; namespace sub3 { struct nQuery { int r, k; }; int trace[N][2]; vector<nQuery> vec[N]; bool check () { rep (i, 1, Q) if (qr[i].k != 1 && qr[i].k != qr[i].r - qr[i].l + 1) return 0; return 1; } void solution() { rep (i, 1, n) a[i] = 3; rep (i, 1, Q) { // rep (j, 1, n) cout << a[j] <<" "; if (qr[i].k == qr[i].r - qr[i].l + 1) { if (qr[i].val == 0) { rep (j, qr[i].l, qr[i].r) a[j] = 0; } else { vec[qr[i].l].pb({qr[i].r, 1}); } } else { if (qr[i].val == 1) { rep (j, qr[i].l, qr[i].r) if (a[j] == 0) { cout << -1 <<"\n"; return; } else a[j] = 1; } else { vec[qr[i].l].pb({qr[i].r, 0}); } } } // rep (i, 1, n) // cout << a[i] <<" "; // cout <<"\n"; memset(trace, -1, sizeof trace); trace[0][0] = trace[0][1] = 0; // cout <<"hihi\n"; rep (i, 1, n) rep (c, 0, 1) { reb (j, i, 1) { if (a[j] != 3 && a[j] != c) break; int ok = 1; iter (&id, vec[j]) { if (id.r > i) continue; if (id.k != c) { ok = 0; break; } } if (!ok) break; if (trace[j - 1][c ^ 1] != -1) { trace[i][c] = j - 1; break; } } // cout << i <<","<<c<<" "<<trace[i][c] <<"\n"; } int c = -1; if (trace[n][0] != -1) c = 0; if (trace[n][1] != -1) c = 1; if (c == -1) { cout << -1 <<"\n"; return; } int pos = n; while (pos > 0) { rep (i, trace[pos][c] + 1, pos) { a[i] = c; } pos = trace[pos][c]; c ^= 1; } rep (i, 1, n) cout <<a[i] <<" "; } } namespace sub1 { void solution () { rep (msk, 0, (1 << n) - 1) { rep (i, 1, n) a[i] = bit(msk, i - 1); bool ok = 1; rep (q, 1, Q) { if (!ok) break; Query &cur = qr[q]; int wanted = cur.val, num; if (wanted == 1) num = cur.r - cur.l + 1 - cur.k + 1; else num = cur.k; rep (i, cur.l, cur.r) { if (num == 0) break; if (a[i] == wanted) --num; } if (num > 0) ok = 0; } if (ok) { rep (i, 1, n) cout << a[i] << " "; cout<<"\n"; return; } } cout << -1 <<"\n"; } } void solution () { cin >> n >> Q; rep (i, 1, Q) { cin >>qr[i].l >> qr[i].r >> qr[i].k >> qr[i].val; ++qr[i].l; ++qr[i].r; } if (n <= 18) sub1 :: solution(); else if (sub3 :: check()) sub3 :: solution(); else { rep (i, 1, n) a[i] = 3; sort (qr + 1, qr + 1 + Q, [] (Query A, Query B) { return A.r < B.r || (A.r == B.r && A.l > B.l); }); rep (q, 1, Q) { Query &cur = qr[q]; int wanted = cur.val, num; if (wanted == 1) num = cur.r - cur.l + 1 - cur.k + 1; else num = cur.k; int x = Rand(0, 1); if (x == 0) { rep (i, cur.l, cur.r) { if (num == 0) break; if (a[i] == 3) a[i] = wanted, --num; else { if (a[i] == wanted) --num; } } } else { reb (i, cur.r, cur.l) { if (num == 0) break; if (a[i] == 3) a[i] = wanted, --num; else { if (a[i] == wanted) --num; } } } if (num > 0) { cout << -1 <<"\n"; return; } } rep (i, 1, n) if (a[i] == 3) a[i] = 0; rep (i, 1, n) { cout << a[i] <<" "; } } } #define file(name) freopen(name".inp","r",stdin); \ freopen(name".out","w",stdout); int main () { // file("c"); ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0); int num_Test = 1; // cin >> num_Test; while (num_Test--) solution(); } /* no bug challenge +2 2 + 8 * 2 - 9 4 5 0 1 1 1 0 2 1 0 2 2 1 0 3 3 1 1 1 2 1 0 1 1 3 3 1 1 0 0 1 1 0 1 */

Compilation message (stderr)

restore.cpp: In function 'void sub1::solution()':
restore.cpp:116:45: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
  116 |             rep (i, 1, n) a[i] = bit(msk, i - 1);
      |                                           ~~^~~
restore.cpp:10:30: note: in definition of macro 'bit'
   10 | #define bit(msk, i) ((msk >> i) & 1)
      |                              ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...