Submission #598983

#TimeUsernameProblemLanguageResultExecution timeMemory
598983wiwihoBit Shift Registers (IOI21_registers)C++17
100 / 100
5 ms1180 KiB
#include "registers.h" #include <bits/stdc++.h> #include <bits/extc++.h> #define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define iter(a) a.begin(), a.end() #define riter(a) a.rbegin(), a.rend() #define lsort(a) sort(iter(a)) #define gsort(a) sort(riter(a)) #define pb(a) push_back(a) #define eb(a) emplace_back(a) #define pf(a) push_front(a) #define ef(a) emplace_front(a) #define pob pop_back() #define pof pop_front() #define mp(a, b) make_pair(a, b) #define F first #define S second #define mt make_tuple #define gt(t, i) get<i>(t) #define tomax(a, b) ((a) = max((a), (b))) #define tomin(a, b) ((a) = min((a), (b))) #define topos(a) ((a) = (((a) % MOD + MOD) % MOD)) #define uni(a) a.resize(unique(iter(a)) - a.begin()) #define printv(a, b) {bool pvaspace=false; \ for(auto pva : a){ \ if(pvaspace) b << " "; pvaspace=true;\ b << pva;\ }\ b << "\n";} using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef unsigned long long ull; typedef long double ld; using pii = pair<int, int>; using pll = pair<ll, ll>; using pdd = pair<ld, ld>; using tiii = tuple<int, int, int>; const ll MOD = 1000000007; const ll MAX = 2147483647; template<typename A, typename B> ostream& operator<<(ostream& o, pair<A, B> p){ return o << '(' << p.F << ',' << p.S << ')'; } ll ifloor(ll a, ll b){ if(b < 0) a *= -1, b *= -1; if(a < 0) return (a - b + 1) / b; else return a / b; } ll iceil(ll a, ll b){ if(b < 0) a *= -1, b *= -1; if(a > 0) return (a + b - 1) / b; else return a / b; } const int B = 2000; int s, n, k, q; void solve0_round(int r){ append_right(1, 0, (1 << r) * k); append_xor(2, 0, 1); if(r == 0) append_and(2, 2, 90); append_print(0); append_print(1); append_print(2); if(k == 1){ append_move(3, 2); } for(int i = 1; i < k; i *= 2){ if(i == 1){ append_right(80, 2, i * 2 >= k ? k - i : i); append_or(3, 2, 80); } else{ append_right(80, 3, i * 2 >= k ? k - i : i); append_or(3, 3, 80); } append_print(3); } append_print(3); append_add(3, 3, 91); append_print(3); append_right(3, 3, 1); append_print(3); append_and(4, 0, 3); if(r == 0) append_and(4, 4, 90); append_add(5, 4, 90); append_and(6, 5, 92); append_right(7, 6, k - 1); append_add(8, 5, 7); append_or(9, 8, 4); append_and(10, 9, 2); for(int i = 0; i <= 10; i++) append_print(i); append_xor(0, 0, 10); append_print(0); } void solve0(){ /* 0: S = A 1: B 2: A xor B 3: highbit of 2 4: A and (3) 5: (4) + 0000 | 1111 | 0000 | 1111 6: (5) & 0000 | 1000 | 0000 | 1000 7: (6) >> (k-1) 8: (5) + (7) 9: (8) or (4) // done 10: (9) and (2) ans: A ^ (10) 90: 0000 | 1111 | 0000 | 1111 91: 0000 | 0001 | 0000 | 0001 92: 0000 | 1000 | 0000 | 1000 80: temp */ int tn = 1; while(tn < n) tn *= 2; vector<bool> tmp(B); for(int i = n * k; i < tn * k; i++) tmp[i] = true; if(tn != n){ append_store(1, tmp); append_or(0, 0, 1); } fill(iter(tmp), false); for(int i = 0; i < tn * k; i++){ if(i / k % 2 == 0) tmp[i] = true; } append_store(90, tmp); fill(iter(tmp), false); for(int i = 0; i < tn; i++){ if(i % 2 == 0) tmp[i * k] = 1; } append_store(91, tmp); append_left(92, 91, k - 1); for(int i = 0; tn > 1; i++, tn /= 2){ if(i == 1) append_and(0, 0, 90); solve0_round(i); } } // ----- vector<vector<pii>> seg; void dfs(int l, int r, int dpt, int mx){ if(dpt == mx) return; seg[dpt].eb(mp(l, r)); if(l == r){ dfs(l, r, dpt + 1, mx); return; } int m = (l + r) / 2; dfs(l, m, dpt + 1, mx); dfs(m + 1, r, dpt + 1, mx); } void setbyte(vector<bool>& tmp, int x){ for(int i = 0; i < k; i++) tmp[x * k + i] = true; } void setbytes(vector<bool>& tmp, int l, int r){ for(int i = l; i <= r; i++) setbyte(tmp, i); } void solve1_get(int rnd, int num){ { vector<bool> tmp(B); for(pii i : seg[rnd]){ int len = i.S - i.F + 1; if(num >= len) continue; setbyte(tmp, i.F); } append_store(86, tmp); } append_print(0); append_print(1); append_print(2); append_print(81); append_print(86); append_and(90, 1, 86); append_and(91, 2, 86); if(k > 1){ append_xor(3, 91, 81); append_add(4, 3, 82); // append_and(5, 4, 81); append_add(6, 4, 90); // R-L append_and(7, 6, 83); // no swap append_right(8, 7, k); append_add(9, 80, 8); } else{ append_xor(92, 90, 91); append_and(8, 92, 90); } append_xor(10, 1, 2); append_and(11, 10, 9); append_xor(1, 1, 11); append_xor(2, 2, 11); append_print(1); append_print(2); append_and(12, 1, 86); append_xor(13, 1, 12); append_right(14, 13, k); append_or(1, 14, 84); append_left(15, 12, num * k); append_or(0, 0, 15); for(int i = 0; i <= 15; i++) append_print(i); } void solve1_round(int rnd){ //cerr << "round " << rnd << "\n"; //printv(seg[rnd], cerr); vector<bool> tmp80(B); vector<bool> tmp81(B); vector<bool> tmp82(B); vector<bool> tmp83(B); vector<bool> tmp84(B); vector<bool> tmp87(B); vector<bool> tmp88(B); for(pii i : seg[rnd]){ int l = i.F, r = i.S; int len = r - l + 1; if(len == 1){ setbyte(tmp87, i.F); } else{ int m = (l + r) / 2; setbytes(tmp80, l, m); setbyte(tmp81, l); tmp81[(l + 1) * k] = true; tmp82[l * k] = true; tmp83[(l + 1) * k] = true; setbyte(tmp84, m); if(len % 2 == 1) setbyte(tmp88, m); } } append_store(80, tmp80); append_store(81, tmp81); append_store(82, tmp82); append_store(83, tmp83); append_store(84, tmp84); append_store(87, tmp87); append_store(88, tmp88); append_and(1, 0, 80); append_move(2, 99); int mx = 0; map<int, vector<pii>> all; for(pii i : seg[rnd]){ int l = i.F, r = i.S; int len = r - l + 1; mx = max(mx, len); if(len == 1) continue; all[len].eb(i); } for(auto& v : all){ int len = (v.F + 1) / 2; vector<bool> tmp(B); for(pii i : v.S){ int l = i.F, r = i.S; int m = (l + r) / 2; setbytes(tmp, m + 1, r); } append_store(90, tmp); append_and(91, 90, 0); append_right(92, 91, len * k); append_or(2, 2, 92); } append_or(2, 2, 88); append_and(90, 0, 87); append_move(0, 99); append_or(0, 0, 90); for(int i = 0; i < mx; i++){ solve1_get(rnd, i); } } void solve1(){ /* 0: S round 1: L = S and (80) 2: R = S >> r and (80) S: clean iter build (86) 90: L and (86) 91: R and (86) 3: (91) xor (81) 4: (3) + (82) // 5: (4) and (81) 6: (4) + (90) = L-R 7: (6) and (83) // no swap 8: (7) >> k 9: (80) + (8) 10: L xor R 11: (10) and (9) L: L xor (11) R: R xor (11) 12: L and (86) 13: L xor (12) 14: (13) >> k L: (14) or (84) 15: (12) << num S: (15) or S 80: |0000|(right)+|1111|(left) 81: |0000|0000|0001|1111|(lr) 82: |0000|0000|0000|0001|(lr) 83: |0000|0000|0001|0000|(lr) 84: |0000|(right)+|1111|0000|0000|(left) X 85: |0000|0000|0001|1111|(lr) 86: |0000|0000|0000|[num<=size]|(lr) 87: |[size=1]|(lr) 88: |0000|(right)+|[len is odd]|0000|0000|(left) 90~98: temp 99: empty */ int d = __lg(n); if((1 << d) < n) d++; //cerr << n << " " << d << "\n"; seg.resize(d); dfs(0, n - 1, 0, d); for(int i = d - 1; i >= 0; i--) solve1_round(i); } void construct_instructions(int _s, int _n, int _k, int _q){ s = _s, n = _n, k = _k, q = _q; if(s == 0) solve0(); else solve1(); }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...