#include "registers.h"
#include <bits/stdc++.h>
using namespace std;
const int M = 100, B = 2000;
void keep_prefix(int x, int l)
{
append_left(x, x, B - l);
append_right(x, x, B - l);
}
void or_numbers(int n, int k, int t, int x)
{
/*
bit or n k-bit numbers stored at first k bits
x: array
10, 11: working space
12: empty filter
t: output
*/
append_move(10, x);
while (n > 1)
{
int m = (n + 1) / 2;
append_right(11, 10, m * k);
append_or(10, 11, 10);
n = m;
}
keep_prefix(10, k);
append_move(t, 10);
}
void construct_instructions(int s, int n, int k, int q)
{
if (s == 0)
{
if (k == 1 && n == 2)
{
append_right(1, 0, 1);
append_and(0, 1, 0);
}
else if (k == 2 && n == 2)
{
// check 2
// if a ^ b == 3 add (a cycle shifted & b > 0)
append_right(1, 0, 2);
append_and(2, 0, 1); // a & b
// append_print(2);
append_right(10, 1, 1);
append_left(11, 1, 1);
append_or(12, 10, 11);
append_left(20, 12, B - 2);
append_right(20, 20, B - 2); // b cycle shifted
// append_print(20);
append_and(20, 0, 20); // a cycle shifted & b
// append_print(20);
append_xor(25, 0, 1); // a ^ b, only 3 is okay so...
append_left(25, 25, B - 2);
append_right(25, 25, B - 2);
// append_print(25);
append_left(26, 25, 1);
append_right(27, 25, 1);
append_or(28, 26, 27); // a ^ b cycle shifted
// append_print(28);
append_and(25, 25, 28); // a ^ b == 3
// append_print(25);
append_and(20, 20, 25); // and with (a cycle shifted & b > 0)
vector<bool> two(B, 0);
two[0] = two[1] = 1;
append_store(30, two);
append_add(31, 30, 20); // third bit is the answer
append_right(31, 31, 2);
append_add(0, 31, 2);
}
else
{
vector<bool> stupid(B, 0), full(B, 1), one(B, 0), kless1(B, 0), everyk(B, 0);
for (int i = 0; i < n * k; i++)
stupid[i] = 1;
one[0] = 1;
for (int i = 0; i < n * k; i++)
if (i % k != k - 1)
kless1[i] = 1;
else
everyk[i] = 1;
append_store(5, stupid);
append_store(6, full);
append_store(7, one);
append_store(8, kless1);
append_store(9, everyk);
append_xor(0, 0, 5);
for (int i = k - 1; i >= 0; i--)
{
vector<bool> filter(B, 0);
for (int j = i; j < n * k; j += k)
filter[j] = 1;
append_store(1, filter);
append_and(2, 0, 1);
append_right(2, 2, i);
// if none of them has the bit, 4 stores all 1 and becomes all zero when added 1,
// thus append_not again and set the filter to all 1
append_not(4, 2);
append_add(4, 4, 7);
append_right(4, 4, B - 1);
append_add(4, 4, 6);
// using 111...110 to duplicate (but not-ed) first k-1 bits
append_add(3, 2, 8);
append_not(3, 3);
append_xor(2, 3, 9);
append_or(2, 4, 2);
append_and(0, 2, 0);
append_print(0);
}
or_numbers(n, k, 0, 0);
append_xor(0, 0, 5);
keep_prefix(0, k);
}
}
else
{
vector<bool> even(B, 0), odd(B, 0);
for (int i = 0; i < (n - 1) * k; i++)
if (i / k % 2 == 0)
even[i] = 1;
else
odd[i] = 1;
append_store(5, even);
append_store(6, odd);
auto bubble = [&](int mask)
{
append_print(0);
append_right(10, 0, k);
append_xor(15, 10, 0);
append_print(15);
append_and(15, 15, mask);
append_move(20, 15);
append_move(35, 99);
for (int i = 1; i < k; i++)
{
append_right(30, 20, i);
append_or(35, 30, 35);
}
append_not(30, 35);
append_and(20, 30, 20);
append_print(20);
append_and(20, 20, mask);
append_print(20);
append_and(40, 20, 0);
append_add(50, 40, mask);
append_right(50, 50, k);
append_and(50, 50, mask);
append_add(50, 50, mask);
append_not(50, 50);
append_and(50, 50, mask);
append_and(15, 50, 15);
append_left(60, 15, k);
append_or(15, 60, 15);
append_print(15);
append_xor(0, 0, 15);
};
for (int i = 0; i <= n; i++)
if (i % 2 == 0)
bubble(5);
else
bubble(6);
// 11010101010101
// 00100000101000
}
}
| # |
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 |
1 ms |
224 KB |
Output is correct |
| 2 |
Correct |
1 ms |
292 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
2 ms |
628 KB |
Output is correct |
| 4 |
Correct |
1 ms |
596 KB |
Output is correct |
| 5 |
Correct |
1 ms |
596 KB |
Output is correct |
| 6 |
Correct |
1 ms |
596 KB |
Output is correct |
| 7 |
Correct |
1 ms |
596 KB |
Output is correct |
