#include "registers.h"
#include <bits/stdc++.h>
using std::array;
using std::pair;
using std::tuple;
using std::vector;
constexpr int M = 100;
constexpr int B = 2000;
namespace ops {
bool locked[B];
bool vacant[B];
void init() {
locked[0] = true;
for (int i = 1; i < M; ++i) {
vacant[i] = true;
}
}
void lock(const int r) {
assert(!locked[r]);
assert(!vacant[r]);
locked[r] = true;
}
void dump(const int r) {
assert(!locked[r]);
assert(!vacant[r]);
vacant[r] = true;
}
void dump_all() {
for (int i = 0; i < M; ++i) {
if (!locked[i] and !vacant[i]) {
dump(i);
}
}
}
int get_free() {
int r = 0;
while (r < M and !vacant[r]) {
r += 1;
}
assert(r != M);
vacant[r] = false;
return r;
}
int copy(const int from) {
assert(0 <= from and from < M);
const int t = get_free();
append_move(t, from);
return t;
}
void debug(const int x) {
assert(0 <= x and x < M);
append_print(x);
}
void copy_to(const int from, const int to) {
assert(0 <= from and from < M);
assert(0 <= to and to < M);
append_move(to, from);
}
int create(const vector<bool>& v) {
assert((int)v.size() == B);
const int t = get_free();
append_store(t, v);
return t;
}
int AND(const int x, const int y) {
assert(0 <= x and x < M);
assert(0 <= y and y < M);
const int t = get_free();
append_and(t, x, y);
return t;
}
int OR(const int x, const int y) {
assert(0 <= x and x < M);
assert(0 <= y and y < M);
const int t = get_free();
append_or(t, x, y);
return t;
}
int XOR(const int x, const int y) {
assert(0 <= x and x < M);
assert(0 <= y and y < M);
const int t = get_free();
append_xor(t, x, y);
return t;
}
int ADD(const int x, const int y) {
assert(0 <= x and x < M);
assert(0 <= y and y < M);
const int t = get_free();
append_add(t, x, y);
return t;
}
int NOT(const int x) {
assert(0 <= x and x < M);
const int t = get_free();
append_not(t, x);
return t;
}
int LEFT(const int x, const int s) {
assert(0 <= x and x < M);
assert(0 <= s and s <= B);
const int t = get_free();
append_left(t, x, s);
return t;
}
int RIGHT(const int x, const int s) {
assert(0 <= x and x < M);
assert(0 <= s and s <= B);
const int t = get_free();
append_right(t, x, s);
return t;
}
}
void solve_minimum(const int N, const int K) {
for (int d = 1; d < N; d *= 2) {
vector<bool> X(B), Y(B), Z(B, true);
for (int i = 0; i + d < N; i += 2 * d) {
for (int j = i * K; j < (i + 1) * K; ++j) {
X[j] = true;
Y[j + d * K] = true;
Z[j] = false;
Z[j + d * K] = false;
}
}
const int x = ops::AND(ops::create(X), 0);
const int y = ops::RIGHT(ops::AND(ops::create(Y), 0), d * K);
const int sum = ops::ADD(ops::NOT(x), y);
const int swap = ops::RIGHT(sum, K);
const int stay = ops::NOT(swap);
const int small = ops::OR(ops::AND(swap, y), ops::AND(stay, x));
const int large = ops::OR(ops::AND(swap, x), ops::AND(stay, y));
if (N == 2) {
ops::copy_to(ops::OR(small, ops::LEFT(large, d * K)), 0);
} else {
ops::copy_to(ops::OR(ops::OR(small, ops::LEFT(large, d * K)), ops::AND(0, ops::create(Z))), 0);
}
ops::dump_all();
}
}
void solve_sort(const int N, const int K) {
array<int, 2> x, y, z;
for (int k = 0; k < 2; ++k) {
vector<bool> X(B), Y(B), Z(B, true);
for (int i = k; i + 1 < N; i += 2) {
for (int j = i * K; j < (i + 1) * K; ++j) {
X[j] = true;
Y[j + K] = true;
Z[j] = false;
Z[j + K] = false;
}
}
x[k] = ops::create(X);
y[k] = ops::create(Y);
z[k] = ops::create(Z);
ops::lock(x[k]);
ops::lock(y[k]);
ops::lock(z[k]);
}
for (int step = 0; step < N; ++step) {
const int k = step % 2;
const int p = ops::AND(x[k], 0);
const int q = ops::RIGHT(ops::AND(y[k], 0), K);
const int sum = ops::ADD(ops::NOT(p), q);
const int swap = ops::RIGHT(sum, K);
const int stay = ops::NOT(swap);
const int small = ops::OR(ops::AND(swap, q), ops::AND(stay, p));
const int large = ops::OR(ops::AND(swap, p), ops::AND(stay, q));
ops::copy_to(ops::OR(ops::OR(small, ops::LEFT(large, K)), ops::AND(0, z[k])), 0);
ops::dump_all();
}
}
void construct_instructions(int Subtask, int N, int K, int) {
ops::init();
if (Subtask == 0) {
solve_minimum(N, K);
} else {
solve_sort(N, K);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
300 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
304 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
468 KB |
Output is correct |
| 4 |
Correct |
1 ms |
468 KB |
Output is correct |
| 5 |
Correct |
1 ms |
468 KB |
Output is correct |
| 6 |
Correct |
1 ms |
468 KB |
Output is correct |
| 7 |
Correct |
1 ms |
468 KB |
Output is correct |
