Submission #1153572

#TimeUsernameProblemLanguageResultExecution timeMemory
1153572zhasynUnscrambling a Messy Bug (IOI16_messy)C++20
100 / 100
2 ms1844 KiB
#include "messy.h" #include <bits/stdc++.h> #define pb push_back #define pf push_front using namespace std; #define F first #define S second typedef long long ll; #define pii pair <int, int> #define pll pair <ll, ll> typedef long double ld; const ll N = 128 + 100, M = 1e7 + 10, len = 21, inf = 1e18; const ll mod = 998244353; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); ll um(ll a, ll b){ return (1LL * a * b) % mod; } ll subr(ll a, ll b){ return ((1LL * a - b) % mod + mod) % mod; } int n, cnt, pos[N], per[N]; string orig = ""; void calc(int l, int r){ //cout << l << " "<< r << endl; if(r - l == 1) return; int mid = (l + r) / 2; calc(l, mid); calc(mid, r); string s = orig; for(ll i = 0; i < l; i++){ s[i] = '1'; } for(ll i = r; i < n; i++){ s[i] = '1'; } for(ll i = l; i < mid; i++){ s[i] = '1'; add_element(s); s[i] = '0'; } } vector <int> over; vector <int> nums[N][N]; bool need[N]; string nw; void gt(int from, int to, int l = 0, int r = n){ if(from <= l && r <= to) return; int mid = (r + l) / 2; if(to <= mid){ for(auto u : nums[mid][r]){ nw[u] = '1'; } gt(from, to, l, mid); } else{ for(auto u : nums[l][mid]){ nw[u] = '1'; } gt(from, to, mid, r); } } vector<int> restore_permutation(int nx, int w, int r){ n = nx; for(int i = 0; i < n; i++){ orig += '0'; } calc(0, n); for(int i = 0; i < n; i++){ nums[0][n].pb(i); } compile_set(); vector <int> vec; for(int len = n; len >= 2; len /= 2){ for(int i = 0; i < n; i += len){ nw = orig; gt(i, i + len); //cout << nw << " nw\n"; int mid = i + len/2; for(auto u : nums[i][i + len]){ need[u] = true; //cout << u << " upd\n"; } for(auto u : nums[i][i + len]){ nw[u] = '1'; bool rs = check_element(nw); if(rs){ for(int k = 0; k < (int)nw.size(); k++){ if(nw[k] == '1' && need[k]){ nums[i][mid].pb(k); need[k] = false; } } } nw[u] = '0'; } for(auto u : nums[i][i + len]){ if(need[u]) nums[mid][i + len].pb(u); need[u] = false; } } } for(int i = 0; i < n; i++){ pos[nums[i][i + 1][0]] = i; } for(int i = 0; i < n; i++){ vec.pb(pos[i]); } return vec; }

Compilation message (stderr)

messy.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
messy_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
#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...