//Challenge: Accepted
#include "registers.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 400005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const int M = 100;
const int B = 2000;
void chmin(int K, int sw) {
append_not(2, 1);
append_and(2, 2, 98);
append_add(2, 2, 97);
append_add(2, 2, 0);
append_right(3, 2, K);
append_and(3, 3, 97);
{
int tmp = K;
int i = 0;
while (tmp) {
if (tmp <= (1<<i)) {
append_left(4, 3, tmp);
append_or(3, 3, 4);
tmp = 0;
} else {
append_left(4, 3, (1<<i));
append_or(3, 3, 4);
tmp -= 1<<i;
}
i++;
}
}
append_not(4, 3);
append_and(8, 1, 4);
append_and(9, 0, 3);
if (sw) {
append_and(10, 0, 4);
append_and(11, 1, 3);
append_add(1, 10, 11);
}
append_add(0, 8, 9);
}
void solvemin(int N, int K) {
if (N == 1) return;
append_right(1, 0, K * (N / 2) * 2);
append_and(1, 1, 99);
append_print(0);
append_print(1);
chmin(K, 0);
solvemin((N + 1) / 2, K);
}
void sortlayer(int N, int K, vector<int> sep) {
append_print(0);
if (sep.size() == N+1) return;
vector<bool> se(B, 0);
vector<int> nxt;
int dis = 0;
for (int i = 1;i < sep.size();i++) {
if (sep[i] - sep[i-1] > 1) {
dis = max(dis, sep[i] - sep[i-1] - 1);
int p = (sep[i-1] + sep[i]) / 2;
for (int j = p;j < sep[i];j++) {
for (int e = 0;e < 2*K;e++) se[j*2*K + e] = 1;
}
nxt.push_back(p);
}
}
append_store(51, se);
append_not(52, 51);
append_print(52);
append_or(1, 52, 0);
append_and(0, 52, 0);
append_print(0);
append_print(1);
append_move(49, 69); //clear 49
for (int i = 1;i <= dis;i++) {
append_right(1, 1, 2*K);
chmin(K, 1);
append_print(69);
append_print(0);
append_print(1);
append_and(2, 1, 50);
append_left(2, 2, i * 2*K);
append_or(49, 49, 2);
}
append_left(1, 1, 2*K*dis);
append_or(1, 1, 49);
append_and(1, 1, 51);
append_or(0, 0, 1);
sep.insert(sep.end(), nxt.begin(), nxt.end());
sort(sep.begin(), sep.end());
sortlayer(N, K, sep);
}
void construct_instructions(int tasktype, int N, int K, int q) {
//special case for K=1
if (K == 1) {
vector<bool> odd(B, 0);
for (int i = 1;i < B;i += 2) odd[i] = 1;
append_store(80, odd);
append_not(81, 80);
append_and(1, 0, 80);
append_print(1);
if (N % 2 == 0) append_left(1, 1, N - 1);
else append_left(1, 1, N);
append_or(0, 0, 1);
append_and(0, 0, 81);
append_print(0);
K = 2;
}
//assuming K >=2
vector<bool> st(B, 0), st2(B, 0), ones(B, 0), suf(B, 0);
for (int j = 0;j < 2*N;j += 2) {
for (int i = 0;i < K;i++) {
st[j*K + i] = 1, st2[j*K+i] = 1;
}
ones[j*K] = 1;
st2[(j+1)*K] = 1;
}
for (int i = N*K;i < B;i++) suf[i] = 1;
for (int i = 2*N*K;i < B;i++) st[i] = st2[i] = 1;
if (N > 2) {
append_store(96, suf);
append_or(0, 0, 96);
}
append_store(99, st); //alternate K bits
append_store(98, st2); //alternate K+1 1s, K-1 0s
append_store(97, ones); //1 + 2K-1 0s
append_right(1, 0, K);
append_and(0, 0, 99);
append_and(1, 1, 99);
if (tasktype == 0) {
append_print(0);
append_print(1);
chmin(K, 0);
solvemin((N+1) / 2, K);
append_print(0);
append_print(1);
} else {
vector<bool> fi(B, 0), tmp(B, 0);
for (int i = 0;i < K;i++) fi[i] = 1;
append_store(50, fi);
int siz = (N+1) / 2;
for (int i = 0;i < siz*2*K;i++) tmp[i] = 1;
append_store(48, tmp);
for (int i = 0;i < siz;i++) {
if (i) {
append_right(2, 1, (siz-1)* 2*K);
append_and(2, 2, 50);
append_left(1, 1, 2*K);
append_or(1, 2, 1);
}
chmin(K, 1);
}
append_and(0, 0, 48);
if (siz % 2) {
append_right(2, 1, (siz-1)* 2*K);
append_and(2, 2, 50);
append_left(1, 1, 2*K);
append_or(1, 2, 1);
}
append_left(1, 1, siz * 2 * K);
append_or(0, 0, 1);
vector<int> vec = {0, siz, N};
sortlayer(N, K, vec);
for (int i = 0;i < N;i++) {
int l = 2*i*K;
append_left(1, 0, B - (2*i*K + K));
append_right(1, 1, B - l);
append_left(1, 1, i*K);
append_or(69, 1, 69);
}
append_move(0, 69);
}
}
/*
0 4 3 1000
1 3 4 2
*/
Compilation message
registers.cpp: In function 'void sortlayer(int, int, std::vector<int>)':
registers.cpp:70:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
70 | if (sep.size() == N+1) return;
| ~~~~~~~~~~~^~~~~~
registers.cpp:75:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for (int i = 1;i < sep.size();i++) {
| ~~^~~~~~~~~~~~
| # |
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 |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
300 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
300 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Incorrect sorting |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Incorrect sorting |
| 2 |
Halted |
0 ms |
0 KB |
- |
