oj.uz

Submission #645462

# Submission time Handle Problem Language Result Execution time Memory
645462 2022-09-27T07:32:38 Z jamezzz Bit Shift Registers (IOI21_registers) C++17
100 / 100
 1 ms 468 KB 
#include "registers.h"
#include <bits/stdc++.h>
using namespace std;

#define bits 2000

void compare(int k){//compares and swaps if a>b
	append_right(1,0,k);
	append_and(0,0,98);//$0=a
	append_and(1,1,98);//$1=b
	
	append_not(2,1);//$2=^b
	append_add(3,0,2);//$3=a-b
	append_right(3,3,k);//$3=1111 if a<b
	
	append_and(4,0,3);//$4=a if a<b else 0
	append_and(5,1,3);//$5=b if a<b else 0
	
	append_not(3,3);//$3=1111 if a>b
	append_and(6,0,3);//$6=a if a>b else 0
	append_and(7,1,3);//$7=b if a>b else 0
	
	append_or(8,4,7);//$8=min(a,b)
	append_or(9,5,6);//$9=max(a,b)
	
	append_left(9,9,k);
	append_or(0,8,9);
}

void construct_instructions(int s,int n,int k,int q){
	if(s==0){
		int jmp=2;
		vector<bool> v;
		v.resize(bits);
		for(int i=0;i<bits;++i){
			if(i/k>=n)v[i]=true;
		}
		append_store(98,v);//mask
		while(n!=1){
			append_or(0,0,98);
			
			for(int i=0;i<bits;++i){
				if((i/k)%jmp==0)v[i]=true;
				else v[i]=false;
			}
			append_store(99,v);
			
			append_right(1,0,jmp/2*k);
			append_and(0,0,99);//$0=a
			append_and(1,1,99);//$1=b
			
			append_not(2,1);//$2=^b
			append_add(3,0,2);//$3=a-b
			append_right(3,3,k);//$3=1111 if a<b
			
			append_and(4,0,3);//$4=b/0
			
			append_not(3,3);//$3=1111 if a<b
			append_and(5,1,3);//$5=a/0
			
			append_or(0,4,5);
			
			n=(n+1)/2;
			jmp*=2;
		}
	}
	else{
		vector<bool> v;
		v.resize(bits);
		for(int i=0;i<bits;++i){
			if(i/k>=n)v[i]=true;
		}
		append_store(99,v);//mask
		append_or(0,0,99);
		
		for(int i=0;i<bits;++i){
			if((i/k)%2==0)v[i]=true;
			else v[i]=false;
		}
		append_store(98,v);
		
		for(int i=0;i<bits;++i){
			if(i<k)v[i]=true;
			else v[i]=false;
		}
		append_store(96,v);
		
		for(int i=0;i<(n+1)/2;++i){
			compare(k);
			
			append_and(95,0,96);
			append_right(0,0,k);
			
			compare(k);
			
			append_left(0,0,k);
			append_or(0,0,95);
		}
	}
}

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 212 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 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 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 212 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 212 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 428 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