oj.uz

Submission #599758

# Submission time Handle Problem Language Result Execution time Memory
599758 2022-07-19T20:27:09 Z idiot123 Bit Shift Registers (IOI21_registers) C++17
64 / 100
 2 ms 596 KB 
#include "registers.h"

using namespace std;

const int shift = 2;
const int b = 2000;
const int m = 100;

void construct_instructions(int s, int n, int k, int q) {
	//first we need to make space between numbers
	//if(s == 1){
		vector<bool> v(b, false);
		//oddReg and evenReg can be used to separate numbers on odd and even positions
		int oddReg = 99;
		for(int i = 1; i < n; i+=2){
			for(int j = k*i; j < k*i + k; j++)v[j] = 1;
		}
		append_store(oddReg, v);
		for(int i = 0; i < b; i++)v[i] = 0;
		for(int i = 0; i < n; i+=2){
			for(int j = k*i; j < k*(i+1); j++)v[j] = 1;
		}
		int evenReg = 98;
		append_store(evenReg, v);
		int aReg = 1; int bReg = 2;
		append_and(aReg, evenReg, 0);
		append_and(bReg, oddReg, 0);
		append_right(bReg, bReg, k);
		int evenSwapRange = 96; int oddSwapRange = 97;
		append_right(oddReg, oddReg, k);
		append_and(evenSwapRange, oddReg, evenReg);
		append_left(oddReg, oddReg, 2*k);
		append_and(oddSwapRange, oddReg, evenReg);
		append_right(oddReg, oddReg, k);
		int c, d, e, f; c = 3; d = 4; e = 5; f= 6;
		int swap = 7; int antiSwap = 8;
		int signReg = 9; int negateReg = 10;
		int addReg = 11;
		for(int i = 0; i < b; i++)v[i] = 0;
		for(int i = 0; i < n; i+= 2){
			v[k*i + k] = 1;
		}
		append_store(signReg, v);
		append_right(addReg, signReg, k);
		append_or(negateReg, signReg, evenReg);
		for(int i = 0; i < n; i++){
			if(i % 2 == 0){
				if(k == 1){
					append_not(swap, bReg);
					append_and(swap, swap, aReg);
				}else{
					append_xor(swap, aReg, negateReg);
					append_add(swap, swap, addReg);
					append_add(swap, swap, bReg);
					append_and(swap, swap, signReg);
					//na tym etapie na pojedynczych bitach jest znak, trzeba go rozmazac o k pozycji w prawo
					int xd = 1;
					while(2 * xd <= k + 1){
						append_right(antiSwap, swap, xd);
						append_or(swap, swap, antiSwap);
						xd *= 2;
					}
					if(xd < k + 1){
						append_right(antiSwap, swap, k + 1 - xd);
						append_or(swap, swap, antiSwap);
					}
					//swap powinien byc juz gotowy
				}
				append_and(swap, swap, evenSwapRange);//ograniczamy zakres swapa
				append_not(antiSwap, swap);
				append_and(c, aReg, antiSwap);
				append_and(d, aReg, swap);
				append_and(e, bReg, antiSwap);
				append_and(f, bReg, swap);
				
				append_add(aReg, c, f);
				append_add(bReg, d, e);
			}else{
				append_left(bReg, bReg, 2*k);
				
				if(k == 1){
					append_not(swap, aReg);
					append_and(swap, swap, bReg);
				}else{
					append_xor(swap, bReg, negateReg);
					append_add(swap, swap, addReg);
					append_add(swap, swap, aReg);
					append_and(swap, swap, signReg);
					//na tym etapie na pojedynczych bitach jest znak, trzeba go rozmazac o k pozycji w prawo
					int xd = 1;
					while(2 * xd <= k + 1){
						append_right(antiSwap, swap, xd);
						append_or(swap, swap, antiSwap);
						xd *= 2;
					}
					if(xd < k + 1){
						append_right(antiSwap, swap, k + 1 - xd);
						append_or(swap, swap, antiSwap);
					}
					//swap powinien byc juz gotowy
				}
				append_and(swap, swap, oddSwapRange);//ograniczamy zakres swapa
				append_not(antiSwap, swap);
				append_and(c, aReg, antiSwap);
				append_and(d, aReg, swap);
				append_and(e, bReg, antiSwap);
				append_and(f, bReg, swap);
				
				append_add(aReg, c, f);
				append_add(bReg, d, e);
				
				append_right(bReg, bReg, 2*k);
			}
		}
		append_left(bReg, bReg, k);
		append_add(0, aReg, bReg);
	//}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #2
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Wrong answer detected in grader
2 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Wrong answer detected in grader
2 Halted 0 ms 0 KB -

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct

Subtask #6
29.0 / 29.0

# 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 2 ms 596 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct