oj.uz

Submission #535606

# Submission time Handle Problem Language Result Execution time Memory
535606 2022-03-10T16:30:44 Z benson1029 Bit Shift Registers (IOI21_registers) C++17
100 / 100
 2 ms 468 KB 
#include "registers.h"
#include<bits/stdc++.h>
using namespace std; 

vector<bool> tmp;

void construct_instructions(int s, int n, int k, int q) {
	if(s==0 && q==20) {
		if(k==1) {
			append_right(1, 0, 1);
			append_and(0, 0, 1);
		} else {
			for(int i=0; i<k; i++) tmp.push_back(true);
			for(int i=k; i<2000; i++) tmp.push_back(false);
			append_store(99, tmp);
			append_right(1, 0, 2);
			append_and(2, 0, 99);
			append_and(77, 1, 2);
			append_add(10, 1, 99); append_right(10, 10, 2);
			append_add(11, 2, 99); append_right(11, 11, 2);
			append_and(10, 10, 11);
			append_add(12, 77, 99); append_right(12, 12, 2);
			append_xor(10, 10, 12);
			append_or(0, 77, 10);
		}
	} else if(s==0) {
		 tmp.clear();
		 for(int i=0; i<n*k; i++) {
		 	tmp.push_back(true);
		 }
		 for(int i=n*k; i<2000; i++) {
		 	tmp.push_back(false);
		 }
		 append_store(99, tmp); // 11111...1111
		 tmp.clear();
		 tmp.push_back(true);
		 for(int i=1; i<2000; i++) {
		 	tmp.push_back(false);
		 }
		 append_store(98, tmp); // 000...0001
		 tmp.clear();
		 for(int i=0; i<k; i++) tmp.push_back(true);
		 for(int i=k; i<2000; i++) tmp.push_back(false);
		 append_store(97, tmp);
		 append_xor(0, 0, 99);
		 for(int i=k-1; i>=0; i--) {
		 	tmp.clear();
		 	for(int j=0; j<n*k; j++) {
		 		if(j%k==i) tmp.push_back(true);
		 		else tmp.push_back(false);
			 }
			 for(int j=n*k; j<2000; j++) tmp.push_back(false);
			 append_store(10, tmp);
			 append_and(10, 0, 10);
			 append_left(9, 10, k-i);
			 append_right(8, 10, i);
			 append_not(8, 8);
			 append_add(8, 8, 98);
			 append_add(8, 8, 9);
			 // 8 stores the mask, 7 used
			 append_add(7, 8, 99);
			 append_right(7, 7, n*k);
			 append_add(7, 7, 99);
			 append_xor(8, 7, 8);
			 append_and(0, 0, 8);
		 }
		 for(int i=0; i<7; i++) {
		 	append_right(1, 0, k*(1<<i));
		 	append_or(0, 0, 1);
		 }
		 append_and(0, 0, 97);
		 append_xor(0, 0, 97);
	} else {
		tmp.clear();
		tmp.push_back(true);
		for(int i=1; i<2000; i++) {
			tmp.push_back(false);
		}
		append_store(98, tmp); // 000...0001
		tmp.clear();
		for(int i=0; i<n*k; i++) {
			if((i/k)%2==1) tmp.push_back(true);
			else tmp.push_back(false);
		}
		for(int i=n*k; i<2000; i++) tmp.push_back(false);
		append_store(90, tmp);
		tmp.clear();
		for(int i=0; i<n*k; i++) {
			if((i/k)%2==0 && (i/k)>0) tmp.push_back(true);
			else tmp.push_back(false);
		}
		for(int i=n*k; i<2000; i++) tmp.push_back(false);
		append_store(80, tmp);
		tmp.clear();
		for(int i=0; i<2000; i++) tmp.push_back(false);
		for(int i=k*2; i<=n*k; i+=k*2) {
			tmp[i] = true;
		}
		append_store(91, tmp);
		tmp.clear();
		for(int i=0; i<2000; i++) tmp.push_back(false);
		for(int i=k*3; i<=n*k; i+=k*2) {
			tmp[i] = true;
		}
		append_store(81, tmp);
		for(int i=0; i<(n+1)/2; i++) {
			// 0&1, 2&3, etc.
			append_left(10, 0, k);
			append_and(20, 10, 90); 
			append_and(21, 0, 90);
			append_or(10, 20, 91);
			append_not(11, 21);
			append_add(11, 11, 98);
			append_add(10, 10, 11);
			append_and(10, 10, 91);
			append_right(11, 10, k*2);
			append_not(11, 11);
			append_add(11, 11, 98);
			append_add(10, 11, 10);
			// register 10: swap or not
			append_right(30, 21, k);
			append_or(30, 30, 20);
			append_and(30, 30, 10);
			append_not(31, 10);
			append_and(31, 31, 0);
			append_or(0, 30, 31);
			
			// 1&2, 3&4, etc.
			append_left(10, 0, k);
			append_and(20, 10, 80);
			append_and(21, 0, 80);
			append_or(10, 20, 81);
			append_not(11, 21);
			append_add(11, 11, 98);
			append_add(10, 10, 11);
			append_and(10, 10, 81);
			append_right(11, 10, k*2);
			append_not(11, 11);
			append_add(11, 11, 98);
			append_add(10, 11, 10);
			// register 10: swap or not
			append_right(30, 21, k);
			append_or(30, 30, 20);
			append_and(30, 30, 10);
			append_not(31, 10);
			append_and(31, 31, 0);
			append_or(0, 30, 31);
		}
	}
}

Subtask #1
10.0 / 10.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
25.0 / 25.0

# 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 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #5
13.0 / 13.0

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

Subtask #6
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 432 KB Output is correct
5 Correct 1 ms 428 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 432 KB Output is correct