#include "registers.h"
#include <vector>
#include <iostream>
#define loop(a, b) for(int a = 0; a < b; a++)
constexpr int TASK_MIN = 0;
constexpr int TASK_SORT = 1;
constexpr int BIT_COUNT = 2000;
constexpr int REGISTER_1 = 99;
constexpr int REGISTER_2K = 98;
constexpr int REGISTER_C = 97;
constexpr int REGISTER_EXTRA = 96;
constexpr int REGISTER_IO = 0;
constexpr int REGISTER_A = 1;
constexpr int REGISTER_B = 2;
void sortPrepare(int s, int n, int k, int q) {
// constants
std::vector<bool> gen_1(BIT_COUNT);
loop(a, n/2 + 1) gen_1[(a+1) * (2*k) - 1] = 1;
append_store(REGISTER_1, gen_1);
std::vector<bool> gen_2k(BIT_COUNT);
loop(a, n/2 + 1) loop(b, k) gen_2k[(a+1) * (2*k) - (b+1)] = 1;
append_store(REGISTER_2K, gen_2k);
std::vector<bool> gen_c(BIT_COUNT);
loop(a, n/2 + 1) gen_c[(a+1) * (2*k) - k] = 1;
append_store(REGISTER_C, gen_c);
std::vector<bool> gen_extra(BIT_COUNT);
loop(a, 2*k) gen_extra[n * k + a] = 1;
append_store(REGISTER_EXTRA, gen_extra);
// extra char
append_or(REGISTER_IO, REGISTER_IO, REGISTER_EXTRA);
// shift the A
append_left(REGISTER_A, REGISTER_IO, k);
// mask both A and B
append_and(REGISTER_B, REGISTER_IO, REGISTER_2K);
append_and(REGISTER_A, REGISTER_A, REGISTER_2K);
}
void sortSmaller(int s, int n, int k, int q, int REGISTER_SMALL, int REGISTER_BIG) {
constexpr int REGISTER_NB = 3;
append_not(REGISTER_NB, REGISTER_B);
append_and(REGISTER_NB, REGISTER_NB, REGISTER_2K);
constexpr int REGISTER_SUM = 4;
append_add(REGISTER_SUM, REGISTER_A, REGISTER_NB);
constexpr int REGISTER_SUM_CARRY = 5;
append_right(REGISTER_SUM_CARRY, REGISTER_SUM, k);
append_and(REGISTER_SUM_CARRY, REGISTER_SUM_CARRY, REGISTER_C);
constexpr int REGISTER_MASK2 = 7;
append_add(REGISTER_MASK2, REGISTER_SUM_CARRY, REGISTER_2K);
append_and(REGISTER_MASK2, REGISTER_MASK2, REGISTER_2K);
constexpr int REGISTER_MASK1 = 6;
append_not(REGISTER_MASK1, REGISTER_MASK2);
constexpr int REGISTER_PARTA1 = 8;
constexpr int REGISTER_PARTA2 = 9;
constexpr int REGISTER_PARTB2 = 10;
constexpr int REGISTER_PARTB1 = 11;
append_and(REGISTER_PARTA1, REGISTER_A, REGISTER_MASK1);
append_and(REGISTER_PARTA2, REGISTER_A, REGISTER_MASK2);
append_and(REGISTER_PARTB2, REGISTER_B, REGISTER_MASK2);
append_and(REGISTER_PARTB1, REGISTER_B, REGISTER_MASK1);
append_or(REGISTER_BIG, REGISTER_PARTA1, REGISTER_PARTB2);
append_or(REGISTER_SMALL, REGISTER_PARTA2, REGISTER_PARTB1);
}
void sort_shake(int s, int n, int k, int q) {
sortSmaller(s, n, k, q, REGISTER_A, REGISTER_B);
append_left(REGISTER_B, REGISTER_B, 2*k);
sortSmaller(s, n, k, q, REGISTER_B, REGISTER_A);
append_right(REGISTER_B, REGISTER_B, 2*k);
}
void construct_instructions(int s, int n, int k, int q) {
if (s == TASK_SORT) {
sortPrepare(s, n, k, q);
// append_print(REGISTER_IO);
// append_print(REGISTER_A);
// append_print(REGISTER_B);
loop(a, n / 2){
sort_shake(s, n, k, q);
// append_print(REGISTER_A);
// append_print(REGISTER_B);
}
if (n % 2 == 1) sortSmaller(s, n, k, q, REGISTER_A, REGISTER_B);
append_right(REGISTER_A, REGISTER_A, k);
append_or(REGISTER_IO, REGISTER_A, REGISTER_B);
}
else if (s == TASK_MIN) {
sortPrepare(s, n, k, q);
// append_print(REGISTER_IO);
// append_print(REGISTER_A);
// append_print(REGISTER_B);
while (n > 1) {
sortSmaller(s, n, k, q, REGISTER_A, REGISTER_B);
n = (n + 1) / 2;
append_right(REGISTER_B, REGISTER_A, (2*k) * (n/2) );
// append_print(REGISTER_A);
// append_print(REGISTER_B);
}
append_right(REGISTER_A, REGISTER_A, k);
append_or(REGISTER_IO, REGISTER_A, REGISTER_B);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Wrong answer detected in grader |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
288 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
0 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
296 KB |
Output is correct |
| 2 |
Correct |
1 ms |
288 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
296 KB |
Output is correct |
| 2 |
Correct |
1 ms |
288 KB |
Output is correct |
| 3 |
Correct |
1 ms |
460 KB |
Output is correct |
| 4 |
Correct |
2 ms |
416 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
