//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);
//if you're reading this on oj.uz and find it basically unreadable, I sincerely apologize.
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);
chmin(K, 0);
solvemin((N + 1) / 2, K);
}
void sortlayer(int N, int K, vector<int> sep) {
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]+1) / 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_or(1, 52, 0);
append_and(0, 52, 0);
append_move(49, 69); //clear 49
if (sep.size() == 3) {
append_or(0, 51, 0);
append_and(0, 0, 99);
int dif = nxt[0];
append_right(1, 1, nxt[0] * 2 * K);
append_and(1, 1, 99);
vector<bool> cl(B, 0), reset(B, 0);
for (int i = 1;i < sep.size();i++) {
for (int j = 0;j < K;j++) cl[(sep[i]-1)*2*K+j] = 1;
}
for (int i:nxt) {
for (int j = 0;j < K;j++) reset[i*2*K + j] = 1;
}
append_store(48, cl);
append_store(47, reset);
append_not(46, 50);
for (int i = 0;i < dif;i++) {
chmin(K, 1);
append_right(2, 1, (dif-1)* 2*K);
append_and(2, 2, 50);
append_left(1, 1, 2*K);
append_and(1, 1, 46);
append_or(1, 2, 1);
append_or(1, 1, 47);
}
append_and(0, 0, 52);
append_left(1, 1, 2*K*dif);
append_and(1, 1, 51);
append_or(0, 0, 1);
} else {
for (int i = 1;i <= dis;i++) {
append_right(1, 1, 2*K);
append_or(1, 1, 41);
append_and(1, 1, 99);
chmin(K, 1);
append_and(2, 1, 40);
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
bool onebit = 0;
if (K == 1) {
onebit = 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);
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);
K = 2;
}
vector<bool> st(B, 0), st2(B, 0), ones(B, 0), suf(B, 0);
for (int i = N*K;i < B;i++) suf[i] = 1;
if (N > 2) {
append_store(96, suf);
append_or(0, 0, 96);
if (N % 2) N++;
}
//assuming K >=2
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 = 2*N*K;i < B;i++) st[i] = st2[i] = 1;
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) {
chmin(K, 0);
solvemin((N+1) / 2, K);
} else {
vector<bool> fi(B, 0), tmp(B, 0), ending(B, 0);
for (int i = 0;i < K;i++) fi[i] = 1, ending[B - K - 1 - i] = 1;
append_store(50, fi);
append_store(41, ending);
append_move(40, 50);
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++) {
chmin(K, 1);
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_and(0, 0, 48);
append_left(1, 1, siz * 2 * K);
append_or(0, 0, 1);
for (int i = 0;i < K;i++) fi[siz*2*K+i] = 1;
append_store(50, fi);
vector<int> vec = {0, siz, N};
sortlayer(N, K, vec);
for (int i = 0;i < N;i++) {
append_left(1, 0, B - (2*i*K + K));
if (onebit) {
append_right(1, 1, B - 2);
append_left(1, 1, i);
} else {
append_right(1, 1, B - K);
append_left(1, 1, i*K);
}
append_or(69, 1, 69);
}
append_move(0, 69);
}
}
/*
0 4 3 1000
1 3 4 2
9 28 73 7 162 493 22 88 37 66 44
*/
Compilation message
registers.cpp: In function 'void sortlayer(int, int, std::vector<int>)':
registers.cpp:69:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
69 | if (sep.size() == N+1) return;
| ~~~~~~~~~~~^~~~~~
registers.cpp:74:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for (int i = 1;i < sep.size();i++) {
| ~~^~~~~~~~~~~~
registers.cpp:97:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for (int i = 1;i < sep.size();i++) {
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 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 |
0 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 |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
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 |
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 |
2 ms |
632 KB |
Output is correct |
| 4 |
Correct |
2 ms |
632 KB |
Output is correct |
| 5 |
Correct |
1 ms |
632 KB |
Output is correct |
| 6 |
Correct |
1 ms |
596 KB |
Output is correct |
| 7 |
Correct |
2 ms |
596 KB |
Output is correct |
