Submission #600901

#TimeUsernameProblemLanguageResultExecution timeMemory
600901MadokaMagicaFanBit Shift Registers (IOI21_registers)C++17
100 / 100
1 ms628 KiB
#include "bits/stdc++.h" using namespace std; using ll = long long; const ll inf = 1e9; const int md1 = 1e9+7; const int md2 = 998244353; #define sz(v) ((int)v.size()) #define pb push_back #define pry cout << "YES\n" #define prn cout << "NO\n" #define endl '\n' #define fst first #define scn second #define clear for (i = 0; i < B; ++i) { v[i] = 0; } /* #define ONPC */ const int D = 99; // del extra const int L = 98; // last bit const int S = 97; // for sum const int N = 96; // min const int X = 95; // max const int F = 94; // diff const int T = 93; // temporary const int R = 92; // removable const int B = 2000; const int M = 100; vector<bitset<B>> r(M); void append_move(int t, int y); void append_store(int t, vector<bool> v); void append_and(int t, int x, int y); void append_or(int t, int x, int y); void append_xor(int t, int x, int y); void append_not(int t, int x); void append_left(int t, int x, int p); void append_right(int t, int x, int p); void append_add(int t, int x, int y); void fminmax(int a, int b, int k, bool onlymin) { append_not(F, b); append_and(F ,F, D); append_add(F ,F, a); append_and(F ,F, L); int s = 0; for (int j = 0; j < B; ++j) { if ((1<<(j+1))-1 > k) break; s = (1<<(j+1))-1; append_right(N, F, (1<<j)); append_or(F,F,N); } if (s < k) { append_right(T, F, k-s); append_or(F,F,T); } if (onlymin) { append_and(0, F, b); append_not(F,F); append_and(T, F, a); append_or(0, 0, T); } else { append_and(X, F, a); append_and(N, F, b); append_xor(T, X, a); append_xor(F, N, b); append_or(N, N, T); append_or(X, X, F); } return; } int domin(int n, int k) { int i, j, l, lastbit; vector<bool> v(B, 0); lastbit = 31-__builtin_clz(n); for (i = n * k; i < B; ++i) v[i] = 1; if (n != (1<<lastbit)) { append_store(3,v); append_or(0,0,3); n = (1<<(1+lastbit)); } clear; for (i = 0; i < n; ++i) { if (i&1) continue; for (j = 0; j < k; ++j) v[i*k+j] = 1; } append_store(D,v); clear; for (i = 0; i < n; ++i) { if (i&1) continue; v[i*k+k] = 1; } append_store(L,v); clear; int diff = k; int s = 0; while (n > 1) { append_and(1, s, D); append_right(2, s, diff); fminmax(1,2,k, 1); diff <<= 1; n >>= 1; } return 0; } void construct_instructions(int s, int n, int k, int q) { int i, j, l, it; if (!s) { domin(n,k); return; } vector<bool> v(B, 0); for (i = n * k; i < B; ++i) v[i] = 1; append_store(3,v); clear; if (n&1) { ++n; append_or(0,0,3); } it = n + 5; for (i = 0; i < n; ++i) { if (i&1) continue; for (j = 0; j < k; ++j) v[i*k+j] = 1; } append_store(D,v); clear; for (i = 0; i < n; ++i) { if (i&1) continue; v[i*k+k] = 1; } append_store(L,v); clear; for (i = 0; i < k; ++i) v[i] = 1; for (i = (n-1) * k; i < B; ++i) v[i] = 1; append_store(R,v); clear; for (i = 0; i < it; ++i) { if (i & 1) { append_right(1, 0, k); append_and(1, 1, D); append_right(2, 0, k<<1); append_and(2, 2, D); fminmax(1,2,k,0); append_and(0,0,R); append_left(T, N, k); append_or(0,0,T); append_left(T, X, k<<1); append_or(0,0,T); } else { append_and(1, 0, D); append_right(2, 0, k); append_and(2, 2, D); fminmax(1,2,k,0); append_move(0,N); append_left(T, X, k); append_or(0,0,T); } } return; } #ifdef ONPC int op = 0; void append_move(int t, int y){ ++op; r[t] = r[y]; } void append_store(int t, vector<bool> v){ ++op; for (int i = 0; i < B; ++i) r[t][i] = v[i]; } void append_and(int t, int x, int y){ ++op; r[t] = (r[x]&r[y]); } void append_or(int t, int x, int y){ ++op; r[t] = (r[x]|r[y]); } void append_xor(int t, int x, int y){ ++op; r[t] = (r[x]^r[y]); } void append_not(int t, int x){ ++op; r[t] = (~r[x]); } void append_left(int t, int x, int p){ ++op; r[t] = (r[x]<<p); } void append_right(int t, int x, int p){ ++op; r[t] = (r[x]>>p); } void append_add(int t, int x, int y){ ++op; bitset<B> tmp; bool ex = 0; int cnt; for (int i = 0; i < B; ++i) { tmp[i] = (r[x][i]^r[y][i]^ex); cnt = 0; if (r[x][i]) ++cnt; if (r[y][i]) ++cnt; if (ex) ++cnt; ex = (cnt > 1); } r[t] = tmp; } void solve() { for (int i = 0; i < M; ++i) { for (int j = 0; j < B; ++j) { r[i][j] = 0; } } int n, k, x, rans; rans = inf; cin >> n >> k; for (int i = 0; i < n; ++i) { cin >> x; rans = min(x,rans); for (int j = 0; j < k; ++j) if ((x>>j)&1) r[0][i*k+j] = 1; } construct_instructions(1,n,k,100); /* int ans = 0; */ /* */ /* for (int j = 0; j < n; ++j) { */ /* ans = 0; */ /* for (int i = 0; i < k; ++i) { */ /* if (r[0][j*k+i]) ans |= (1<<i); */ /* } */ /* cout << ans << ' '; */ /* } */ /* cout << endl; */ cout << op << endl; } int32_t main(int argc, char **argv) { if (argc >= 2) { freopen(argv[1], "r", stdin); } else ios_base::sync_with_stdio(0);cin.tie(0); int t = 1; /* cin >> t; */ while(t--) solve(); } #endif

Compilation message (stderr)

registers.cpp: In function 'int domin(int, int)':
registers.cpp:86:15: warning: unused variable 'l' [-Wunused-variable]
   86 |     int i, j, l, lastbit;
      |               ^
registers.cpp: In function 'void construct_instructions(int, int, int, int)':
registers.cpp:134:15: warning: unused variable 'l' [-Wunused-variable]
  134 |     int i, j, l, it;
      |               ^
#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...