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

This is the latest submission verdict.

[2024-11-13 19:38:33]
Judged

Verdict: 100
Time: 5ms
Memory: 4276kb

Show

[2024-11-13 19:38:32]
Submitted

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;
		}
	}
}
*/

Source code, Language: C++20

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