#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;
#ifndef WAIMAI
#include "registers.h"
#endif
#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() { cout << "\n"; }
template<typename T, typename...U>
void dout(T t, U...u) { cout << t << (sizeof...(u) ? ", " : ""), dout(u...); }
#else
#define debug(...) 7122
#endif
#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for(int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second
#ifdef WAIMAI
void append_move(int t, int x);
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 s);
void append_right(int t, int x, int s);
void append_add(int t, int x, int y);
void append_print(int t);
#endif
const int B = 2000;
void construct_instructions(int s, int n, int k, int q) {
if (s == 0) {
vector<bool> mask(B), one(B);
if (n != 1 << __lg(n)) {
FOR (i, n * k, B - 1) mask[i] = 1;
append_store(50, mask);
append_or(0, 0, 50);
}
n = 1 << (__lg(n - 1) + 1);
if (k == 1) {
for (int len = n >> 1; len >= 1; len >>= 1) {
append_right(1, 0, len * k);
append_and(0, 0, 1);
}
return;
}
for (int len = 2; len <= n; len <<= 1) {
fill(mask.begin(), mask.end(), 0);
fill(one.begin(), one.end(), 0);
for (int i = 0; i < n; i += len) {
one[i * k] = 1;
FOR (j, 0, k - 1) mask[i * k + j] = 1;
}
append_store(50, mask);
append_store(51, one);
append_right(1, 0, len * k / 2);
append_and(0, 0, 50);
append_and(1, 1, 50);
append_not(2, 1);
for (int i = 0; i < n; i += len) mask[(i + 1) * k] = 1;
append_store(52, mask);
append_and(2, 2, 52);
append_add(2, 2, 51);
append_add(2, 2, 0);
append_right(2, 2, k);
append_and(2, 2, 51);
append_not(2, 2);
append_and(2, 2, 50);
append_add(2, 2, 51);
append_not(3, 2);
append_and(0, 0, 2);
append_and(1, 1, 3);
append_or(0, 0, 1);
}
return;
}
vector<bool> mask[2], one[2], mid[2], mask2[2];
mask[0] = mask[1] = one[0] = one[1] = mid[0] = mid[1] = mask2[0] = mask2[1] = vector<bool>(B);
FOR (f, 0, 1) {
int m = (n - f) / 2;
fill(mid[f].begin(), mid[f].end(), 1);
FOR (i, 0, m - 1) {
one[f][2 * i * k] = mask2[f][(2 * i + 1) * k] = 1;
FOR (j, 0, k - 1) {
mask[f][2 * i * k + j] = mask2[f][2 * i * k + j] = 1;
mid[f][(2 * i + f) * k + j] = mid[f][(2 * i + f + 1) * k + j] = 0;
}
}
}
append_store(50, mask[0]);
append_store(51, mask[1]);
append_store(52, one[0]);
append_store(53, one[1]);
append_store(54, mid[0]);
append_store(55, mid[1]);
append_store(56, mask2[0]);
append_store(57, mask2[1]);
FOR (t, 0, n - 1) {
int f = t & 1, m = (n - f) / 2;
if (m == 0) continue;
append_right(1, 0, f * k);
append_right(2, 0, (f + 1) * k);
append_and(1, 1, 50 + f);
append_and(2, 2, 50 + f);
if (k == 1) {
append_and(3, 1, 2);
append_xor(2, 1, 2);
append_xor(1, 2, 3);
append_left(3, 3, f * k);
append_left(1, 1, (f + 1) * k);
append_and(0, 0, 54 + f);
append_or(0, 0, 1);
append_or(0, 0, 3);
continue;
}
append_not(3, 2);
append_and(3, 3, 56 + f);
append_add(3, 3, 52 + f);
append_add(3, 3, 1);
append_right(3, 3, k);
append_and(3, 3, 52 + f);
append_not(3, 3);
append_and(3, 3, 50 + f);
append_add(3, 3, 52 + f);
append_not(4, 3);
append_and(3, 3, 1);
append_and(4, 4, 2);
append_or(3, 3, 4);
append_xor(2, 1, 2);
append_xor(1, 2, 3);
append_left(3, 3, f * k);
append_left(1, 1, (f + 1) * k);
append_and(0, 0, 54 + f);
append_or(0, 0, 1);
append_or(0, 0, 3);
}
}
/*
in1
0 2 1 1000
0 0
0 1
1 0
1 1
-1
out1
move 1 0
right 1 1 1
and 0 0 1
0
0
0
1
in2
1 2 1 1000
0 0
0 1
1 0
1 1
-1
out2
move 1 0
right 1 1 1
and 2 0 1
or 3 0 1
left 3 3 1
or 0 2 3
0 0
0 1
0 1
1 1
*/
#ifdef WAIMAI
#ifdef _MSC_VER
# define NORETURN __declspec(noreturn)
#elif defined __GNUC__
# define NORETURN __attribute__ ((noreturn))
#else
# define NORETURN
#endif
static const int m = 100;
static const int b = 2000;
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;
static const int id_print = 9;
static int s, n, k, q;
static int instruction_count = 0;
static bitset<b> reg[m];
static inline void load_register(bitset<b>& bs, vector<int>& v) {
bs.reset();
for (int i = 0; i < (int)v.size(); i++) {
for (int j = 0; j < k; j++) {
bs[i * k + j] = (v[i] & (1 << j));
}
}
}
static inline void unload_register(bitset<b>& bs, vector<int>& v) {
v.assign(v.size(), 0);
for (int i = 0; i < (int)v.size(); i++) {
for (int j = 0; j < k; j++) {
v[i] |= (bs[i * k + j] << j);
}
}
}
static void execute_move(int t, int x) {
reg[t] = reg[x];
}
static void execute_store(int t, vector<bool> v) {
for(int i=0; i<b; i++) {
reg[t][i] = v[i]; // bit-by-bit copy
}
}
static void execute_and(int t, int x, int y) {
reg[t] = (reg[x]®[y]);
}
static void execute_or(int t, int x, int y) {
reg[t] = (reg[x]|reg[y]);
}
static void execute_xor(int t, int x, int y) {
reg[t] = (reg[x]^reg[y]);
}
static void execute_not(int t, int x) {
reg[t] = (~reg[x]);
}
static void execute_left(int t, int x, int p) {
reg[t] = (reg[x]<<p);
}
static void execute_right(int t, int x, int p) {
reg[t] = (reg[x]>>p);
}
static void execute_add(int t, int x, int y) {
bitset<b> tmp;
bool carry = false;
for(int i = 0; i < b; i++) {
tmp[i] = (reg[x][i] ^ reg[y][i] ^ carry);
carry = (reg[x][i] & reg[y][i]) || (reg[x][i] & carry) || (reg[y][i] & carry); // discard the last carry
}
reg[t] = tmp;
}
static void execute_print(int t) {
vector<int> v(n);
unload_register(reg[t], v);
printf("register %d: ", t);
for (int i = 0; i < n; i++) {
printf("%d%c", v[i], i < n - 1 ? ' ' : '\n');
}
}
struct instruction {
int type, t, x, y;
vector<bool> v;
instruction(int _type): type(_type), t(-1), x(-1), y(-1) {}
void execute() {
switch(type) {
case id_move:
execute_move(t, x);
break;
case id_store:
execute_store(t, v);
break;
case id_and:
execute_and(t, x, y);
break;
case id_or:
execute_or(t, x, y);
break;
case id_xor:
execute_xor(t, x, y);
break;
case id_not:
execute_not(t, x);
break;
case id_left:
execute_left(t, x, y);
break;
case id_right:
execute_right(t, x, y);
break;
case id_add:
execute_add(t, x, y);
break;
case id_print:
execute_print(t);
break;
default:
assert(false);
}
}
void print() {
switch(type) {
case id_move:
printf("move %d %d\n", t, x);
break;
case id_store:
printf("store %d ", t);
for(int i=0; i<b; i++) {
putchar(v[i]+'0');
}
putchar('\n');
break;
case id_and:
printf("and %d %d %d\n", t, x, y);
break;
case id_or:
printf("or %d %d %d\n", t, x, y);
break;
case id_xor:
printf("xor %d %d %d\n", t, x, y);
break;
case id_not:
printf("not %d %d\n", t, x);
break;
case id_left:
printf("left %d %d %d\n", t, x, y);
break;
case id_right:
printf("right %d %d %d\n", t, x, y);
break;
case id_add:
printf("add %d %d %d\n", t, x, y);
break;
case id_print:
printf("print %d\n", t);
break;
default:
assert(false);
}
}
};
static vector<instruction> instructions;
NORETURN static inline void error(string reason) {
printf("%s\n", reason.c_str());
fflush(stdout);
exit(0);
}
static inline void check_instructions() {
if (instruction_count >= q) {
error("Too many instructions");
}
}
static inline void check_index(int index) {
if (index < 0 || index >= m) {
error("Invalid index");
}
}
void append_move(int t, int x) {
check_instructions();
check_index(t);
check_index(x);
instruction i(id_move);
i.t = t;
i.x = x;
instruction_count++;
instructions.push_back(i);
}
void append_store(int t, vector<bool> v) {
check_instructions();
check_index(t);
if ((int)v.size() != b) {
error("Value to store is not b bits long");
}
instruction i(id_store);
i.t = t;
i.v = v;
instruction_count++;
instructions.push_back(i);
}
void append_and(int t, int x, int y) {
check_instructions();
check_index(t);
check_index(x);
check_index(y);
instruction i(id_and);
i.t = t;
i.x = x;
i.y = y;
instruction_count++;
instructions.push_back(i);
}
void append_or(int t, int x, int y) {
check_instructions();
check_index(t);
check_index(x);
check_index(y);
instruction i(id_or);
i.t = t;
i.x = x;
i.y = y;
instruction_count++;
instructions.push_back(i);
}
void append_xor(int t, int x, int y) {
check_instructions();
check_index(t);
check_index(x);
check_index(y);
instruction i(id_xor);
i.t = t;
i.x = x;
i.y = y;
instruction_count++;
instructions.push_back(i);
}
void append_not(int t, int x) {
check_instructions();
check_index(t);
check_index(x);
instruction i(id_not);
i.t = t;
i.x = x;
instruction_count++;
instructions.push_back(i);
}
void append_left(int t, int x, int p) {
check_instructions();
check_index(t);
check_index(x);
if (p < 0 || p > b) {
error("Invalid shift value");
}
instruction i(id_left);
i.t = t;
i.x = x;
i.y = p;
instruction_count++;
instructions.push_back(i);
}
void append_right(int t, int x, int p) {
check_instructions();
check_index(t);
check_index(x);
if (p < 0 || p > b) {
error("Invalid shift value");
}
instruction i(id_right);
i.t = t;
i.x = x;
i.y = p;
instruction_count++;
instructions.push_back(i);
}
void append_add(int t, int x, int y) {
check_instructions();
check_index(t);
check_index(x);
check_index(y);
instruction i(id_add);
i.t = t;
i.x = x;
i.y = y;
instruction_count++;
instructions.push_back(i);
}
void append_print(int t) {
check_index(t);
instruction i(id_print);
i.t = t;
instructions.push_back(i);
}
int main() {
assert(4 == scanf("%d %d %d %d", &s, &n, &k, &q));
construct_instructions(s, n, k, q);
for(instruction &i : instructions) {
i.print();
}
vector<int> a(n);
bool exited = false;
while (true) {
for (int i = 0; i < n; i++) {
assert(1 == scanf("%d", &a[i]));
if (i == 0 && a[i] == -1) {
fflush(stdout);
exited = true;
break;
}
}
if (exited) break;
load_register(reg[0], a);
for (int i = 1; i < m; i++) {
reg[i].reset();
}
for (instruction& i : instructions) {
i.execute();
}
unload_register(reg[0], a);
if (s == 0) {
printf("%d\n", a[0]);
} else {
for (int i = 0; i < n; i++) {
printf("%d%c", a[i], i == n - 1 ? '\n' : ' ');
}
}
}
printf("number of instructions: %d\n", instruction_count);
return 0;
}
#endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
300 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 |
296 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
300 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 |
304 KB |
Output is correct |
| 5 |
Correct |
1 ms |
300 KB |
Output is correct |
| 6 |
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 |
| # |
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 |
588 KB |
Output is correct |
| 4 |
Correct |
1 ms |
596 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 |
432 KB |
Output is correct |
