#include "registers.h"
#include <bits/stdc++.h>
using namespace std;
static const int id_move = 0;
static const int id_store = 1;
static const int id_and = 2;
static const int id_or = 3;
static const int id_xor = 4;
static const int id_not = 5;
static const int id_left = 6;
static const int id_right = 7;
static const int id_add = 8;
const int B = 2000;
const int MAXN = 1e5+5;
int ids[MAXN];
vector<int> nxt[MAXN];
vector<int> rev[MAXN];
int deg[MAXN];
bool vis[MAXN];
vector<int> topo;
struct op {
vector<bool> v;
bool pr;
int tp = -1;
int x, y;
op() {}
op(vector<bool> v, int tp, bool pr = 0) : v(v), tp(tp), pr(pr) {}
op(int x, int tp, bool pr = 0) : tp(tp), x(x), pr(pr) {}
op(int x, int y, int tp, bool pr = 0) : tp(tp), x(x), y(y), pr(pr) {}
void append(int t) {
x = ids[x];
if (tp != id_left && tp != id_right) y = ids[y];
t = ids[t];
switch(tp) {
case id_move:
append_move(t, x);
break;
case id_store:
append_store(t, v);
break;
case id_and:
append_and(t, x, y);
break;
case id_or:
append_or(t, x, y);
break;
case id_xor:
append_xor(t, x, y);
break;
case id_not:
append_not(t, x);
break;
case id_left:
append_left(t, x, y);
break;
case id_right:
append_right(t, x, y);
break;
case id_add:
append_add(t, x, y);
break;
// case id_print:
// append_print(t);
// break;
default:
assert(false);
}
if (pr) append_print(t);
}
};
op ops[MAXN];
int t = 1;
int n, k;
void make_edge(int x, int y) {
nxt[x].push_back(y);
rev[y].push_back(x);
deg[x]++;
}
int make_move(int y, bool pr = 0) {
// assert(false);
make_edge(y, t);
ops[t] = op(y, id_move, pr);
return t++;
}
int make_store(vector<bool> v) {
// make_edge(y, t);
ops[t] = op(v, id_store);
return t++;
}
int make_and(int x, int y) {
make_edge(x, t);
make_edge(y, t);
ops[t] = op(x, y, id_and);
return t++;
}
int make_or(int x, int y, bool pr = 0) {
make_edge(x, t);
make_edge(y, t);
ops[t] = op(x, y, id_or, pr);
return t++;
}
int make_xor(int x, int y) {
make_edge(x, t);
make_edge(y, t);
ops[t] = op(x, y, id_xor);
return t++;
}
int make_not(int x) {
make_edge(x, t);
// make_edge(y, t);
ops[t] = op(x, id_not);
return t++;
}
int make_left(int x, int y) {
make_edge(x, t);
// make_edge(y, t);
ops[t] = op(x, y, id_left);
return t++;
}
int make_right(int x, int y, bool pr = 0) {
make_edge(x, t);
// make_edge(y, t);
ops[t] = op(x, y, id_right, pr);
return t++;
}
int make_add(int x, int y) {
make_edge(x, t);
make_edge(y, t);
ops[t] = op(x, y, id_add);
return t++;
}
int prefix_spread(int x, bool care) {
// make_move(x, 1);
for (int i = 0; (1<<i) < k; i++) {
int y = make_right(x, (1<<i));
if (care) {
vector<bool> spec(B, 0);//.assign(B, 0);
for (int u = 0; u < B; u += k) {
for (int j = 0; j < k-(1<<i); j++) spec[u+j] = 1;
}
y = make_and(y, make_store(spec));
}
// append_print(x);
// append_print(y);
// make_move(y, 1);
x = make_or(x, y, 1);
}
return x;
}
int make_min(int x, int y, bool care) { // also free x and y
// make_move(x, 1);
// make_move(y, 1);
int u = make_and(x, make_not(y));
int v = make_and(y, make_not(x));
u = make_and(u, make_not(prefix_spread(v, care)));
u = prefix_spread(u, care);
int xy = make_and(u, make_xor(x, y));
return make_xor(x, xy);
}
void dfs(int cur) {
topo.push_back(cur);
vis[cur] = 1;
for (int v: nxt[cur]) {
if (!vis[v]) dfs(v);
}
}
void construct_instructions(int s, int N, int K, int q) {
n = N; k = K;
assert(s == 0);
// append_print(0);
// make_not(0);
// make_move(0, 1);
int u = 0;
// for (int i = 1; i < 100; i++) avail.insert(i);
for (int b = 0; (1<<b)<n; b++) {
// cerr << (k<<b) << '\n';
u = make_min(u, make_right(u, k<<b, 1), b>0);
}
// for (int i = 0; i < t; i++) {
// if (!vis[i]) dfs(i);
// }
// reverse(topo.begin(), topo.end());
set<int> avail;
for (int i = 0; i < 100; i++) avail.insert(i);
// set<int> waiting;
for (int v = 0; v < t; v++) {
assert(!avail.empty());
ids[v] = *avail.begin();
avail.erase(ids[v]);
// if (deg[v]) waiting.insert(v);
for (int x: rev[v]) {
deg[x]--;
if (!deg[x]) {
// waiting.erase(x);
avail.insert(ids[x]);
}
}
if (v) {
// cerr << ops[v].tp << '\n';
// cerr << ops[v].x << ' ' << ops[v].y << '\n';
ops[v].append(v);
}
}
append_move(0, ids[u]);
}
Compilation message
registers.cpp: In constructor 'op::op(std::vector<bool>, int, bool)':
registers.cpp:30:6: warning: 'op::tp' will be initialized after [-Wreorder]
30 | int tp = -1;
| ^~
registers.cpp:29:7: warning: 'bool op::pr' [-Wreorder]
29 | bool pr;
| ^~
registers.cpp:33:2: warning: when initialized here [-Wreorder]
33 | op(vector<bool> v, int tp, bool pr = 0) : v(v), tp(tp), pr(pr) {}
| ^~
registers.cpp: In constructor 'op::op(int, int, bool)':
registers.cpp:31:6: warning: 'op::x' will be initialized after [-Wreorder]
31 | int x, y;
| ^
registers.cpp:29:7: warning: 'bool op::pr' [-Wreorder]
29 | bool pr;
| ^~
registers.cpp:34:2: warning: when initialized here [-Wreorder]
34 | op(int x, int tp, bool pr = 0) : tp(tp), x(x), pr(pr) {}
| ^~
registers.cpp: In constructor 'op::op(int, int, int, bool)':
registers.cpp:31:9: warning: 'op::y' will be initialized after [-Wreorder]
31 | int x, y;
| ^
registers.cpp:29:7: warning: 'bool op::pr' [-Wreorder]
29 | bool pr;
| ^~
registers.cpp:35:2: warning: when initialized here [-Wreorder]
35 | op(int x, int y, int tp, bool pr = 0) : tp(tp), x(x), y(y), pr(pr) {}
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
11352 KB |
Incorrect min value |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
11096 KB |
Incorrect min value |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
11100 KB |
Incorrect min value |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
11100 KB |
Wrong answer detected in grader |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
22104 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
22104 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
