/*
*
* get a 1 bit on b10 if x <= y and 0 bit otherwise (in reg2)
* where x is number on bit 0..9 in reg0 and y is number on bit 0..9 in reg1
* z is 11 bit number in reg2 on bit 0..10
* make z -> -y - 1 by doing y ^ 0b11111111111 (11 ones)
* make z -> z + x
* if bit 11 is on in reg2: x <= y since number is still negative
* else: x > y
*
* preset:
* 1 mask 00..0011..1100..0011..11...
* 2 mask 0x10 1 0x9 0x10 1 ...
* 3 mask to save value to regS in offset 0
* 4 mask to save value(s) to regS in offset 1
*
* 1 store potential last value in reg0 into regS with and operator with preset 1bits-mask (if n is odd)
* 1 take all odd numbers from reg0 and copy them to reg1:
* 2 use mask 00..0011..1100..0011..11... to get reg1 with only odd indices
* 3 shift to the left by 10 to align with reg0
* 5 perform above steps to get x ?<= y bits for each number in parallel
* 6 filer out all stray bits by using mask with 0x10 1 0x9 0x10 1 ...
* 7 then shift to the left by 1 and or that on
* 8 then shift to the left by 2 and or that on
* 9 then shift to the left by 4 and or that on
* 10 then shift to the left by 2 and or that on to get 11 ones if b10 was 1 and zeroes otherwise
* 11 then and the resulting mask with reg1 to get potential values where y >= x
* 13 then perform not operator on the mask and perform and operator on reg0 to get values where x > y
* 15 then shift to the right by 10 and or the result to regT to insert the elements
* 17 then set regU to reg0 xor reg1 xor reg2 to get a register with the values with the lesser values
* 18 insert regU into regT with or and move result to reg0
* 19 or in the stored value in regS
*
* repeat above step but starting with index 1
* store value 0 (always) and potential last value (if n is even) like step 1 in above sequence
*
* repeat n times where offset (0 or 1) is alternated between (about half each)
*
*/
#include "registers.h"
#include <bits/stdc++.h>
int s, n, k, q;
int alter = 99;
int bkp1 = 98;
int regS0 = 97;
int regS1 = 96;
int nregS0 = 95;
int nregS1 = 94;
int regStore = 93;
int kp1ones = 92;
int nalter = 91;
// 7 queries
void prepare_masks() {
std::vector <bool> mask(2000, 0);
for (int i = 1; i < n; i += 2) {
int start = i * k;
for (int j = 0; j < k; j++) {
mask[start + j] = 1;
}
}
append_store(alter, mask);
mask.assign(2000, 0);
for (int i = 0; i < n; i += 2) {
int start = i * k + k;
mask[start] = 1;
}
append_store(bkp1, mask);
mask.assign(2000, 0);
if (n & 1) {
int start = (n - 1) * k;
for (int j = 0; j < k; j++) {
mask[start + j] = 1;
}
}
append_store(regS0, mask);
mask.assign(2000, 0);
for (int j = 0; j < k; j++) {
mask[j] = 1;
}
if (~n & 1) {
int start = (n - 1) * k;
for (int j = 0; j < k; j++) {
mask[start + j] = 1;
}
}
append_store(regS1, mask);
append_not(nregS0, regS0);
append_not(nregS1, regS1);
mask.assign(2000, 0);
for (int i = 0; i < n; i += 2) {
int start = i * k;
for (int j = 0; j < k + 1; j++) {
mask[start + j] = 1;
}
}
append_store(kp1ones, mask);
append_not(nalter, alter);
}
// 3 queries
void compare_even_pos() {
append_xor(2, kp1ones, 1);
append_add(2, 2, 0);
append_and(2, 2, bkp1);
}
// 22 queries worst case
void go0() {
append_and(regStore, 0, regS0);
append_and(0, 0, nregS0);
append_and(1, 0, alter);
append_right(1, 1, k);
append_and(0, nalter, 0);
compare_even_pos();
append_right(2, 2, 1);
int left = k - 1;
int sofar = 1;
while (left) {
if (sofar <= left) {
append_right(3, 2, sofar);
append_or(2, 2, 3);
left -= sofar;
sofar <<= 1;
} else {
append_right(3, 2, left);
append_or(2, 2, 3);
break;
}
}
append_and(3, 2, 1);
append_not(2, 2);
append_and(4, 2, 0);
append_or(3, 3, 4);
// now register 3 has value of greater number between the two compared values
append_xor(4, 3, 0);
append_xor(4, 4, 1);
// now register 4 has value of lesser number betweren the two compared values
append_left(3, 3, k);
append_or(0, 4, 3);
// now register 0 has result of bubbel sort step
append_or(0, 0, regStore);
// now register 0 has stray value too
}
// 22 queries worst case
void go1() {
append_and(regStore, 0, regS1);
append_and(0, 0, nregS1);
append_and(1, 0, alter);
append_left(1, 1, k);
append_and(0, nalter, 0);
compare_even_pos();
append_right(2, 2, 1);
int left = k - 1;
int sofar = 1;
while (left) {
if (sofar <= left) {
append_right(3, 2, sofar);
append_or(2, 2, 3);
left -= sofar;
sofar <<= 1;
} else {
append_right(3, 2, left);
append_or(2, 2, 3);
break;
}
}
append_and(3, 2, 1);
append_not(2, 2);
append_and(4, 2, 0);
append_or(3, 3, 4);
// now register 3 has value of greater number between the two compared values
append_xor(4, 3, 0);
append_xor(4, 4, 1);
// now register 4 has value of lesser number betweren the two compared values
append_right(4, 4, k);
append_or(0, 4, 3);
// now register 0 has result of bubbel sort step
append_or(0, 0, regStore);
// now register 0 has stray value too
}
//0 1 2 3 4 5 6 7
//0 2 4 6
//0 4
//0
//0 1 2 3 4 5 6 7 8 9
//0 2 4 6 8
//0 4 8
void solve_s0() {
{
std::vector <bool> mask(2000, 0);
mask.assign(2000, 0);
for (int i = 0; i * k + k < 2000; i += 2) {
int start = i * k + k;
mask[start] = 1;
}
append_store(bkp1, mask);
mask.assign(2000, 0);
for (int i = 0; i * k + k + 1 < 2000; i += 2) {
int start = i * k;
for (int j = 0; j < k + 1; j++) {
mask[start + j] = 1;
}
}
append_store(kp1ones, mask);
}
std::vector <bool> mask(2000, 0);
for (int i = n * k; i < 2000; i++) {
mask[i] = 1;
}
append_store(80, mask);
auto tmp = mask;
std::vector <int> ind_left(n);
std::iota(ind_left.begin(), ind_left.end(), 0);
while ((int) ind_left.size() > 1) {
append_or(0, 0, 80);
if (ind_left.size() & 1) {
ind_left.push_back(ind_left.back() + (ind_left[1] - ind_left[0]));
}
std::vector <int> next_ind;
for (int i = 0; i < (int) ind_left.size(); i += 2) {
next_ind.push_back(ind_left[i]);
}
mask.assign(2000, 0);
for (int i = 1; i < (int) ind_left.size(); i += 2) {
for (int j = ind_left[i] * k; j < ind_left[i] * k + k; j++) {
mask[j] = 1;
}
}
append_store(79, mask);
mask.assign(2000, 0);
for (int i = 0; i < (int) ind_left.size(); i += 2) {
for (int j = ind_left[i] * k; j < ind_left[i] * k + k; j++) {
mask[j] = 1;
}
}
append_store(78, mask);
append_and(1, 0, 79);
append_right(1, 1, (ind_left[1] - ind_left[0]) * k);
append_and(0, 78, 0);
compare_even_pos();
//append_right(2, 2, 1);
int left = k - 1 + 1;
int sofar = 1;
while (left) {
if (sofar <= left) {
append_right(3, 2, sofar);
append_or(2, 2, 3);
left -= sofar;
sofar <<= 1;
} else {
append_right(3, 2, left);
append_or(2, 2, 3);
break;
}
}
append_and(3, 2, 0);
append_not(2, 2);
append_and(4, 2, 1);
append_or(0, 3, 4);
// now register 3 has value of greater number between the two compared values
//append_xor(4, 3, 0);
//append_xor(0, 4, 1);
ind_left = next_ind;
}
}
// 7 + n * 22 queries worst case (n = 100, k = 10 -> 2207)
void construct_instructions(int _s, int _n, int _k, int _q) {
s = _s, n = _n, k = _k, q = _q;
if (!s) {
solve_s0();
return;
}
prepare_masks();
for (int i = 0; i < n; i++) {
if (i & 1) {
go1();
} else {
go0();
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 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 |
300 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 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 |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
596 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 |
468 KB |
Output is correct |
