제출 #1060211

#제출 시각아이디문제언어결과실행 시간메모리
1060211vjudge1레지스터 (IOI21_registers)C++17
64 / 100
2 ms760 KiB
#include "registers.h" #include <bits/stdc++.h> using namespace std; using ii = pair<int, int>; set<int> Liberi; const int B = 2000; int n, k; int BM_sel0, BM_sel1, BM_sel12, BM_k1, BM_plus1, BM_sufix1, BM_sufix2, BM_primul; void get_bm(); void free(int x); int xor0(int a, int b); int and0(int a, int b); int or0(int a, int b); int not0(int a); int plus0(int a, int b); int left(int a, int nr); int right(int a, int nr); int dif(int b, int c) { ///4 operatii int x1 = xor0(BM_k1, c); int minc = plus0(x1, BM_plus1); free(x1); int re = and0(plus0(b, minc), BM_k1); /// (b + not C + 1) & BM_k1 free(minc); return re; } int dif2(int bplus, int c) { ///4 operatii int x1 = xor0(BM_k1, c); int v0 = plus0(bplus, x1); int re = and0(v0, BM_k1); /// (b + not C + 1) & BM_k1 free(x1); free(v0); return re; } int min0(int b, int c) { int bpl = plus0(b, BM_plus1); int d = dif2(bpl, c); /// b - c, 0 / 1, ... int d0 = d; d = and0(d, BM_sel12); int len = 1; while(len <= k) { if(2 * len <= k + 1) { int d1 = or0(d, right(d, len)); free(d); d = d1; len *= 2; } else { int d1 = or0(d, right(d, k + 1 - len)); free(d); d = d1; break; } } int e = and0(d0, not0(d)); /// max(b - c, 0), 0 ... free(d0); free(d); int re = dif2(bpl, e); free(bpl); free(e); return re; } int bubble0(int b, int c) { ///will return min(b1, c1) max(b1, c1) ,.... ///basically a round of bubble sort int bpl = plus0(b, BM_plus1); int d = dif2(bpl, c); /// b - c, 0 / 1, ... int d0 = d; d = and0(d, BM_sel12); int len = 1; while(len <= k) { if(2 * len <= k + 1) { int rightdlen = right(d, len); int d1 = or0(d, rightdlen); free(rightdlen); free(d); d = d1; len *= 2; } else { int rightdk = right(d, k + 1 - len); int d1 = or0(d, rightdk); free(rightdk); free(d); d = d1; break; } } int not0d = not0(d); int e = and0(d0, not0d); /// max(b - c, 0), 0 ... free(not0d); free(d0); free(d); int sum = plus0(c, e); int re1 = left(sum, k); free(sum); int re0 = dif2(bpl, e); free(bpl); free(e); int re = plus0(re0, re1); free(re0); free(re1); return re; } void construct_instructions(int s, int n0, int k0, int q) { for(int i = 1; i <= 100; ++i) free(i); n = n0; k = k0; get_bm(); if(s == 0) { int orig = 0; int a = and0(BM_sel0, orig), b = right(and0(BM_sel1, orig), k); if(n & 1) { b = or0(b, BM_sufix2); } for(int step = 1; (1 << (step - 1)) < n; ++step) { int c = min0(a, b); append_print(c); if((1 << step) >= n) { append_move(0, c); return; } a = or0(c, BM_sufix1); b = right(a, (1 << step) * k); append_print(a); append_print(b); } } else { int c = 0; append_print(0); auto bubso = [&](int root, int len) { int v0 = and0(BM_sel1, root); int a = and0(BM_sel0, root), b = right(v0, k); free(v0); if(len & 1) { int b2 = or0(b, BM_sufix2); free(b); b = b2; } int re = bubble0(a, b); free(a); free(b); return re; }; auto fa_pare = [&]() { int v = bubso(c, n); free(c); c = v; }; auto fa_impare = [&]() { int a0 = and0(BM_primul, c); int r = right(c, k); int r2; r2 = bubso(r, n - 1); free(r); r = r2; r2 = left(r, k); free(r); r = r2; r2 = or0(r, a0); free(r); r = r2; free(a0); free(c); c = r; }; for(int i = 0; i < n / 3 * 2; ++i) { fa_pare(); fa_impare(); } if(c) append_move(0, c); append_print(0); } } int get_reg() { int v = *Liberi.begin(); Liberi.erase(v); return v; } int store_bm(vector<bool> V) { int v = get_reg(); append_store(v, V); return v; } void get_bm() { vector<bool> V(B, false); for(int i = 0; i < n; ++i) { if(!(i & 1)) { for(int j = 0; j < k; ++j) V[i * k + j] = 1; } } BM_sel0 = store_bm(V); /// 11..1 00..0 11..1 etc V.assign(B, false); for(int i = 0; i < n; ++i) { if(i & 1) { for(int j = 0; j < k; ++j) V[i * k + j] = 1; } } BM_sel1 = store_bm(V); V.assign(B, false); for(int i = 0; i < n + 2; ++i) { if(i & 1) { for(int j = 0; j < k; ++j) V[i * k + j] = 1; } } BM_sel12 = store_bm(V); V.assign(B, false); for(int i = 0; i < n; ++i) { if(!(i & 1)) { for(int j = 0; j <= k; ++j) V[i * k + j] = 1; } } BM_k1 = store_bm(V); V.assign(B, false); for(int i = 0; i < n; ++i) { if(!(i & 1)) { V[i * k] = 1; } } BM_plus1 = store_bm(V); V.assign(B, false); for(int i = n; i * k < B; ++i) { if(!(i & 1)) { for(int j = 0; j < k; ++j) if(i * k + j < B) V[i * k + j] = 1; } } BM_sufix1 = store_bm(V); V.assign(B, false); for(int i = n - 2; i * k < B; ++i) { if(!(i & 1)) { for(int j = 0; j < k; ++j) if(i * k + j < B) V[i * k + j] = 1; } } BM_sufix2 = store_bm(V); V.assign(B, false); for(int i = 0; i < k; ++i) V[i] = true; BM_primul = store_bm(V); } void free(int x) { Liberi.insert(x); } int xor0(int a, int b) { int v = get_reg(); append_xor(v, a, b); return v; } int plus0(int a, int b) { int v = get_reg(); append_add(v, a, b); return v; } int or0(int a, int b) { int v = get_reg(); append_or(v, a, b); return v; } int and0(int a, int b) { int v = get_reg(); append_and(v, a, b); return v; } int left(int a, int nr) { int v = get_reg(); append_left(v, a, nr); return v; } int right(int a, int nr) { int v = get_reg(); append_right(v, a, nr); return v; } int not0(int a) { int v = get_reg(); append_not(v, a); return v; }
#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...