QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#743612 | #1145. Bit Shift Registers | TheZone | 100 ✓ | 5ms | 4276kb | C++20 | 7.1kb | 2024-11-13 19:38:32 | 2024-11-13 19:38:33 |
Judging History
answer
#include "registers.h"
#include <bits/stdc++.h>
using namespace std;
const int M=100, B=2000;
int S,N,K,Q;
void fix(int p, int q) { // 4 + 2*ceil(log2(K)) + 1 + 2*ceil(log2(K)) + 5 = 4*ceil(log2(K)) + 10
append_xor(M-1,p,q); // p xor q
append_and(M-2,M-1,p); // p > q
append_and(M-3,M-1,q); // p < q
append_not(M-4,M-3); // !(p < q)
for(int p=1;p<K;p*=2) {
append_right(M-5,M-4,p);
append_and(M-4,M-4,M-5);
}
append_and(M-2,M-2,M-4);
for(int p=1;p<K;p*=2) {
append_right(M-5,M-2,p);
append_or(M-2,M-2,M-5);
}
append_and(M-1,M-1,M-2);
append_xor(M-1,M-1,p);
append_xor(M-2,p,q);
append_move(p,M-1);
append_xor(q,M-2,p);
// min in p, max in q
}
void work(int r, int n, int z) {
append_right(1,0,r);
append_print(1);
append_xor(2,0,1); // a xor b
append_and(3,0,2); // (a > b)
append_and(4,1,2); // (a < b)
append_not(5,4); // !(a < b)
append_print(3);
append_print(5);
vector<bool> v(B);
for(int i=0;i<N;i++) {
if(i%z==0) {
for(int j=0;j<K;j++) v[i*K+j]=true;
}
}
append_store(10,v);
// append_print(10);
append_and(3,3,10);
append_and(5,5,10);
append_print(5);
append_add(6,3,5); // add (a > b) and !(a < b)
append_print(6);
vector<bool> w(B);
for(int i=0;i+z/2<N;i++) {
if(i%z==0) {
w[(i+1)*K]=true;
}
}
append_store(7,w); // trying to extract if we need to swap or no, if the bit is on then need to swap
append_print(7);
append_and(7,6,7); // result of extraction
append_print(7);
int s=0;
for(int p=1;p<=K;p*=2) {
append_right(8,7,min(p,K-s));
append_or(7,7,8);
s+=p;
}
append_print(7);
append_and(9,2,7);
append_xor(0,0,9);
append_print(0);
// want to put result back to register 0
}
void work2(int r, int n, int z, int st) { // r = K, z = 1, n = N, st = 0 / 1
append_right(1,0,r);
append_print(1);
append_xor(2,0,1); // a xor b
append_and(3,0,2); // (a > b)
append_and(4,1,2); // (a < b)
append_not(5,4); // !(a < b)
vector<bool> v(B);
for(int i=st;i<N;i++) {
if((i-st)%z==0) {
for(int j=0;j<K;j++) v[i*K+j]=true;
}
}
append_store(10,v);
append_and(3,3,10);
append_and(5,5,10);
append_add(6,3,5); // add (a > b) and !(a < b)
append_print(6);
vector<bool> w(B);
for(int i=st;i+z/2<N;i++) {
if((i-st)%z==0) {
w[(i+1)*K]=true;
}
}
append_store(7,w); // trying to extract if we need to swap or no, if the bit is on then need to swap
append_and(7,6,7); // result of extraction
append_print(7);
int s=0;
for(int p=1;p<K;p*=2) {
append_left(8,7,min(p,K-s-1));
append_or(7,7,8);
s+=p;
}
append_print(7);
append_not(11,10);
append_print(11);
append_and(12,7,11);
append_right(13,12,K);
append_or(14,12,13); // this is the correct swapping bitsss
append_print(14);
// prepare the "new" a xor b which already swaps position (i,i+1)
vector<bool> V(B);
for(int i=st;i<N;i+=2) {
for(int j=0;j<K;j++) {
V[i*K+j]=true;
}
}
vector<bool> W(B);
for(int i=st+1;i<N;i+=2) {
for(int j=0;j<K;j++) {
W[i*K+j]=true;
}
}
vector<bool> Z(B);
if(st) {
for(int j=0;j<K;j++) {
Z[j]=true;
}
}
append_store(15,V);
append_store(16,W);
append_store(17,Z);
append_and(18,0,17);
append_and(19,0,16);
append_and(20,0,15);
append_print(18);
append_print(19);
append_print(20);
append_right(21,19,K);
append_left(22,20,K);
append_print(21);
append_print(22);
append_or(23,21,22);
append_or(24,23,18);
append_print(24);
append_xor(25,0,24);
append_and(26,25,14);
append_xor(0,0,26);
append_print(0);
// want to put result back to register 0
}
void construct_instructions(int S, int N, int K, int Q) {
::S=S, ::N=N, ::K=K, ::Q=Q;
append_print(0);
if(S==0) {
int r=K,n=N,z=1;
while(n>1) {
work(r,n,(1<<z));
r*=2;
n=(n+1)/2;
z++;
}
} else {
// work2(K,N,(1<<1),1);
for(int it=0;it<N;) {
work2(K,N,(1<<1),0);
it++;
if(it>=N) break;
work2(K,N,(1<<1),1);
it++;
}
}
return;
}
/*#include "registers.h"
#include <bits/stdc++.h>
using namespace std;
const int M=100, B=2000;
int S,N,K,Q;
void fix(int p, int q) { // 4 + 2*ceil(log2(K)) + 1 + 2*ceil(log2(K)) + 5 = 4*ceil(log2(K)) + 10
append_xor(M-1,p,q); // p xor q
append_and(M-2,M-1,p); // p > q
append_and(M-3,M-1,q); // p < q
append_not(M-4,M-3); // !(p < q)
for(int p=1;p<K;p*=2) {
append_right(M-5,M-4,p);
append_and(M-4,M-4,M-5);
}
append_and(M-2,M-2,M-4);
for(int p=1;p<K;p*=2) {
append_right(M-5,M-2,p);
append_or(M-2,M-2,M-5);
}
append_and(M-1,M-1,M-2);
append_xor(M-1,M-1,p);
append_xor(M-2,p,q);
append_move(p,M-1);
append_xor(q,M-2,p);
// min in p, max in q
}
void work(int r, int n, int z) {
append_right(1,0,r);
append_print(1);
append_xor(2,0,1); // a xor b
append_and(3,0,2); // (a > b)
append_and(4,1,2); // (a < b)
append_not(5,4); // !(a < b)
append_print(3);
append_print(5);
vector<bool> v(B);
for(int i=0;i<N;i++) {
if(i%z==0) {
for(int j=0;j<K;j++) v[i*K+j]=true;
}
}
append_store(10,v);
// append_print(10);
append_and(3,3,10);
append_and(5,5,10);
append_print(5);
append_add(6,3,5); // add (a > b) and !(a < b)
append_print(6);
vector<bool> w(B);
for(int i=0;i+z/2<N;i++) {
if(i%z==0) {
w[(i+1)*K]=true;
}
}
append_store(7,w); // trying to extract if we need to swap or no, if the bit is on then need to swap
append_print(7);
append_and(7,6,7); // result of extraction
append_print(7);
int s=0;
for(int p=1;p<=K;p*=2) {
append_right(8,7,min(p,K-s));
append_or(7,7,8);
s+=p;
}
append_print(7);
append_and(9,2,7);
append_xor(0,0,9);
append_print(0);
// want to put result back to register 0
}
void work2(int r, int n, int z, int st) { // r = K, z = 1, n = N, st = 0 / 1
append_right(1,0,r);
append_print(1);
append_xor(2,0,1); // a xor b
append_and(3,0,2); // (a > b)
append_and(4,1,2); // (a < b)
append_not(5,4); // !(a < b)
vector<bool> v(B);
for(int i=st;i<N;i++) {
if((i-st)%z==0) {
for(int j=0;j<K;j++) v[i*K+j]=true;
}
}
append_store(10,v);
append_and(3,3,10);
append_and(5,5,10);
append_add(6,3,5); // add (a > b) and !(a < b)
append_print(6);
vector<bool> w(B);
for(int i=st;i+z/2<N;i++) {
if((i-st)%z==0) {
w[(i+1)*K]=true;
}
}
append_store(7,w); // trying to extract if we need to swap or no, if the bit is on then need to swap
append_and(7,6,7); // result of extraction
append_print(7);
int s=0;
for(int p=1;p<K;p*=2) {
append_left(8,7,min(p,K-s-1));
append_or(7,7,8);
s+=p;
}
append_print(7);
append_not(11,10);
append_print(11);
append_and(12,7,11);
append_right(13,12,K);
append_or(14,12,13); // this is the correct swapping bitsss
append_print(14);
// prepare the "new" a xor b which already swaps position (i,i+1)
vector<bool> V(B);
for(int i=st;i<N;i+=2) {
for(int j=0;j<K;j++) {
V[i*K+j]=true;
}
}
vector<bool> W(B);
for(int i=st+1;i<N;i+=2) {
for(int j=0;j<K;j++) {
W[i*K+j]=true;
}
}
}
*/
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 0ms
memory: 3788kb
input:
sc56g857b25lzvk5b9ky5v8ymzqjal4owtshd9qv 0 2 2 1000
output:
vjykoftpkrvoi6c4v1vgep879k0xk83kur2rcdvg OK 17 7 1 0 2 4 2 0 1 2 3 0 2 2 4 1 2 5 5 4 1 10 110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok ac
Subtask #2:
score: 11
Accepted
Test #2:
score: 11
Accepted
time: 0ms
memory: 3756kb
input:
sc56g857b25lzvk5b9ky5v8ymzqjal4owtshd9qv 0 2 2 20
output:
vjykoftpkrvoi6c4v1vgep879k0xk83kur2rcdvg OK 17 7 1 0 2 4 2 0 1 2 3 0 2 2 4 1 2 5 5 4 1 10 110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok ac
Subtask #3:
score: 12
Accepted
Test #3:
score: 12
Accepted
time: 0ms
memory: 3764kb
input:
sc56g857b25lzvk5b9ky5v8ymzqjal4owtshd9qv 0 3 5 4000
output:
vjykoftpkrvoi6c4v1vgep879k0xk83kur2rcdvg OK 38 7 1 0 5 4 2 0 1 2 3 0 2 2 4 1 2 5 5 4 1 10 111110000011111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok ac
Test #4:
score: 12
Accepted
time: 1ms
memory: 4096kb
input:
sc56g857b25lzvk5b9ky5v8ymzqjal4owtshd9qv 0 100 10 4000
output:
vjykoftpkrvoi6c4v1vgep879k0xk83kur2rcdvg OK 147 7 1 0 10 4 2 0 1 2 3 0 2 2 4 1 2 5 5 4 1 10 1111111111000000000011111111110000000000111111111100000000001111111111000000000011111111110000000000111111111100000000001111111111000000000011111111110000000000111111111100000000001111111111000000000011111111...
result:
ok ac
Test #5:
score: 12
Accepted
time: 1ms
memory: 4020kb
input:
sc56g857b25lzvk5b9ky5v8ymzqjal4owtshd9qv 0 89 7 4000
output:
vjykoftpkrvoi6c4v1vgep879k0xk83kur2rcdvg OK 133 7 1 0 7 4 2 0 1 2 3 0 2 2 4 1 2 5 5 4 1 10 11111110000000111111100000001111111000000011111110000000111111100000001111111000000011111110000000111111100000001111111000000011111110000000111111100000001111111000000011111110000000111111100000001111111000000...
result:
ok ac
Test #6:
score: 12
Accepted
time: 0ms
memory: 4028kb
input:
sc56g857b25lzvk5b9ky5v8ymzqjal4owtshd9qv 0 94 9 4000
output:
vjykoftpkrvoi6c4v1vgep879k0xk83kur2rcdvg OK 147 7 1 0 9 4 2 0 1 2 3 0 2 2 4 1 2 5 5 4 1 10 11111111100000000011111111100000000011111111100000000011111111100000000011111111100000000011111111100000000011111111100000000011111111100000000011111111100000000011111111100000000011111111100000000011111111100...
result:
ok ac
Subtask #4:
score: 25
Accepted
Test #7:
score: 25
Accepted
time: 1ms
memory: 4056kb
input:
sc56g857b25lzvk5b9ky5v8ymzqjal4owtshd9qv 0 100 10 150
output:
vjykoftpkrvoi6c4v1vgep879k0xk83kur2rcdvg OK 147 7 1 0 10 4 2 0 1 2 3 0 2 2 4 1 2 5 5 4 1 10 1111111111000000000011111111110000000000111111111100000000001111111111000000000011111111110000000000111111111100000000001111111111000000000011111111110000000000111111111100000000001111111111000000000011111111...
result:
ok ac
Test #8:
score: 25
Accepted
time: 0ms
memory: 3784kb
input:
sc56g857b25lzvk5b9ky5v8ymzqjal4owtshd9qv 0 80 9 150
output:
vjykoftpkrvoi6c4v1vgep879k0xk83kur2rcdvg OK 147 7 1 0 9 4 2 0 1 2 3 0 2 2 4 1 2 5 5 4 1 10 11111111100000000011111111100000000011111111100000000011111111100000000011111111100000000011111111100000000011111111100000000011111111100000000011111111100000000011111111100000000011111111100000000011111111100...
result:
ok ac
Test #9:
score: 25
Accepted
time: 0ms
memory: 3884kb
input:
sc56g857b25lzvk5b9ky5v8ymzqjal4owtshd9qv 0 96 8 150
output:
vjykoftpkrvoi6c4v1vgep879k0xk83kur2rcdvg OK 147 7 1 0 8 4 2 0 1 2 3 0 2 2 4 1 2 5 5 4 1 10 11111111000000001111111100000000111111110000000011111111000000001111111100000000111111110000000011111111000000001111111100000000111111110000000011111111000000001111111100000000111111110000000011111111000000001...
result:
ok ac
Test #10:
score: 25
Accepted
time: 0ms
memory: 4096kb
input:
sc56g857b25lzvk5b9ky5v8ymzqjal4owtshd9qv 0 65 10 150
output:
vjykoftpkrvoi6c4v1vgep879k0xk83kur2rcdvg OK 147 7 1 0 10 4 2 0 1 2 3 0 2 2 4 1 2 5 5 4 1 10 1111111111000000000011111111110000000000111111111100000000001111111111000000000011111111110000000000111111111100000000001111111111000000000011111111110000000000111111111100000000001111111111000000000011111111...
result:
ok ac
Test #11:
score: 25
Accepted
time: 0ms
memory: 3768kb
input:
sc56g857b25lzvk5b9ky5v8ymzqjal4owtshd9qv 0 64 10 150
output:
vjykoftpkrvoi6c4v1vgep879k0xk83kur2rcdvg OK 126 7 1 0 10 4 2 0 1 2 3 0 2 2 4 1 2 5 5 4 1 10 1111111111000000000011111111110000000000111111111100000000001111111111000000000011111111110000000000111111111100000000001111111111000000000011111111110000000000111111111100000000001111111111000000000011111111...
result:
ok ac
Test #12:
score: 25
Accepted
time: 0ms
memory: 3892kb
input:
sc56g857b25lzvk5b9ky5v8ymzqjal4owtshd9qv 0 63 10 150
output:
vjykoftpkrvoi6c4v1vgep879k0xk83kur2rcdvg OK 126 7 1 0 10 4 2 0 1 2 3 0 2 2 4 1 2 5 5 4 1 10 1111111111000000000011111111110000000000111111111100000000001111111111000000000011111111110000000000111111111100000000001111111111000000000011111111110000000000111111111100000000001111111111000000000011111111...
result:
ok ac
Subtask #5:
score: 13
Accepted
Test #13:
score: 13
Accepted
time: 1ms
memory: 3800kb
input:
sc56g857b25lzvk5b9ky5v8ymzqjal4owtshd9qv 1 10 10 4000
output:
vjykoftpkrvoi6c4v1vgep879k0xk83kur2rcdvg OK 360 7 1 0 10 4 2 0 1 2 3 0 2 2 4 1 2 5 5 4 1 10 1111111111000000000011111111110000000000111111111100000000001111111111000000000011111111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok ac
Test #14:
score: 13
Accepted
time: 1ms
memory: 4076kb
input:
sc56g857b25lzvk5b9ky5v8ymzqjal4owtshd9qv 1 8 7 4000
output:
vjykoftpkrvoi6c4v1vgep879k0xk83kur2rcdvg OK 272 7 1 0 7 4 2 0 1 2 3 0 2 2 4 1 2 5 5 4 1 10 11111110000000111111100000001111111000000011111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok ac
Subtask #6:
score: 29
Accepted
Test #15:
score: 29
Accepted
time: 5ms
memory: 4020kb
input:
sc56g857b25lzvk5b9ky5v8ymzqjal4owtshd9qv 1 100 10 4000
output:
vjykoftpkrvoi6c4v1vgep879k0xk83kur2rcdvg OK 3600 7 1 0 10 4 2 0 1 2 3 0 2 2 4 1 2 5 5 4 1 10 111111111100000000001111111111000000000011111111110000000000111111111100000000001111111111000000000011111111110000000000111111111100000000001111111111000000000011111111110000000000111111111100000000001111111...
result:
ok ac
Test #16:
score: 29
Accepted
time: 0ms
memory: 4016kb
input:
sc56g857b25lzvk5b9ky5v8ymzqjal4owtshd9qv 1 91 6 4000
output:
vjykoftpkrvoi6c4v1vgep879k0xk83kur2rcdvg OK 3094 7 1 0 6 4 2 0 1 2 3 0 2 2 4 1 2 5 5 4 1 10 1111110000001111110000001111110000001111110000001111110000001111110000001111110000001111110000001111110000001111110000001111110000001111110000001111110000001111110000001111110000001111110000001111110000001111...
result:
ok ac
Test #17:
score: 29
Accepted
time: 3ms
memory: 4200kb
input:
sc56g857b25lzvk5b9ky5v8ymzqjal4owtshd9qv 1 65 10 4000
output:
vjykoftpkrvoi6c4v1vgep879k0xk83kur2rcdvg OK 2340 7 1 0 10 4 2 0 1 2 3 0 2 2 4 1 2 5 5 4 1 10 111111111100000000001111111111000000000011111111110000000000111111111100000000001111111111000000000011111111110000000000111111111100000000001111111111000000000011111111110000000000111111111100000000001111111...
result:
ok ac
Test #18:
score: 29
Accepted
time: 0ms
memory: 4276kb
input:
sc56g857b25lzvk5b9ky5v8ymzqjal4owtshd9qv 1 64 10 4000
output:
vjykoftpkrvoi6c4v1vgep879k0xk83kur2rcdvg OK 2304 7 1 0 10 4 2 0 1 2 3 0 2 2 4 1 2 5 5 4 1 10 111111111100000000001111111111000000000011111111110000000000111111111100000000001111111111000000000011111111110000000000111111111100000000001111111111000000000011111111110000000000111111111100000000001111111...
result:
ok ac
Test #19:
score: 29
Accepted
time: 0ms
memory: 4204kb
input:
sc56g857b25lzvk5b9ky5v8ymzqjal4owtshd9qv 1 63 10 4000
output:
vjykoftpkrvoi6c4v1vgep879k0xk83kur2rcdvg OK 2268 7 1 0 10 4 2 0 1 2 3 0 2 2 4 1 2 5 5 4 1 10 111111111100000000001111111111000000000011111111110000000000111111111100000000001111111111000000000011111111110000000000111111111100000000001111111111000000000011111111110000000000111111111100000000001111111...
result:
ok ac