Submission #437758

#	Time	Username	Problem	Language	Result	Execution time	Memory
437758		QAQAutoMaton	Bit Shift Registers (IOI21_registers)	C++17	71 / 100	1 ms	620 KiB

registers

#include "registers.h"
#include<bits/stdc++.h>
using namespace std;
const int d=2000;
void construct_instructions(int s, int n, int k, int q) {
	if(s==0){
		vector<bool> vt(d,1);
		append_store(2,vt);
		for(int i=0;i<d;++i)vt[i]=0;
		for(int i=0;i<n;++i)vt[(i+1)*k-1]=1;
		append_store(1,vt);
		for(int i=k-1;~i;--i){
			append_and(3,0,1);
			append_xor(3,1,3);
			//a[3]=(a[1]&a[0])^a[1]
			append_add(4,2,3);
			append_right(4,4,d-1);
			//a[4]=min&1
			append_left(5,4,i);
			append_or(6,6,5);
			if(i){
				append_add(7,2,4);
				append_not(7,7);
				// a[7]=(a[4]=1?~0:0)
				append_and(7,7,1);
				// a[7]=a[4]==1?a[1]:0
				
				append_or(1,3,7);
				append_right(1,1,1);
			}
		}
		append_move(0,6);
	}
	else{
		vector<bool> vt(d,0);
		for(int i=0;i<k;++i)vt[i]=1;
		append_store(50,vt);
		for(int i=0;i<k;++i)vt[i+k]=1;
		//append_print(50);
		append_store(49,vt);
		append_not(3,3);
		for(int i=n-1;~i;--i)for(int j=i;j+1<n;++j){
			append_right(1,0,j*k);
			append_right(2,0,(j+1)*k);
			append_and(1,1,50);
			append_and(2,2,50);

			append_not(4,1);
			//flip 1=> 4
			append_add(5,2,4);
			append_right(5,5,d-1);
			// 1 iff a[1]>=a[2] => 5
			append_add(6,3,5);
			// 111 if a[1]<a[2] else 0 => 6
			append_not(7,6);	
			// 111 if a[1]>=a[2] else 0 => 7
			append_and(8,6,1);
			append_and(9,7,2);
			append_and(6,6,2);
			append_and(7,7,1);
			append_or(1,8,9);
			append_or(2,6,7);
			append_left(48,49,j*k);
			append_not(48,48);
			append_and(0,0,48);
			append_left(1,1,j*k);
			append_left(2,2,(j+1)*k);


			append_or(0,0,1);
			append_or(0,0,2);
		}
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 25 / 25
• Subtask 5: 13 / 13
• Subtask 6: 0 / 29