#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 time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Wrong answer detected in grader |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Wrong answer detected in grader |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
432 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
432 KB |
Output is correct |
| 3 |
Correct |
2 ms |
760 KB |
Output is correct |
| 4 |
Correct |
2 ms |
760 KB |
Output is correct |
| 5 |
Correct |
1 ms |
604 KB |
Output is correct |
| 6 |
Correct |
2 ms |
604 KB |
Output is correct |
| 7 |
Correct |
1 ms |
604 KB |
Output is correct |
