oj.uz

Submission #437254

# Submission time Handle Problem Language Result Execution time Memory
437254 2021-06-26T06:09:47 Z errorgorn Bit Shift Registers (IOI21_registers) C++17
35 / 100
 5 ms 1032 KB 
#include "registers.h"

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back

#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);s<e?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int B=2000;

int s,n,k,q;

const int ALLFLIP=70;
const int ONE=10;
const int AF=11;

void get_min(int n,int k,int ans){ //put the value in ans
	const int ARR=69;
	append_move(ARR,0);
	
	vector<bool> c(B,0);
	append_store(ans,c);
	
	rep(bit,k,0){
		const int ALLBIT=71;
		vector<bool> ab(B,0);
		rep(x,0,n) ab[x*k+bit]=1;
		append_store(ALLBIT,ab);
		
		const int kbit=1,temp=2;
		
		append_move(kbit,ARR);
		
		//append_print(kbit);
		
		int curr=n;
		while (curr>1){
			int p=(curr)/2;
			
			append_right(temp,kbit,p*k);
			append_and(kbit,kbit,temp);
			
			curr=(curr+1)/2;
		}
		
		//the bit either contains 0 or 1 now
		//append_print(kbit);
		
		vector<bool> v2(B,0);
		v2[bit]=1;
		append_store(temp,v2);
		append_and(kbit,kbit,temp);
		
		append_or(ans,ans,kbit); //add to answer if its 1
		
		if (bit==0) continue;
		
		append_xor(kbit,kbit,temp);
		
		append_add(kbit,kbit,ALLFLIP);
		append_not(kbit,kbit);
		append_and(kbit,kbit,ALLBIT);
		
		//make sure kbit only activates for the numbers with flippped k-bit
		append_and(kbit,kbit,ARR);
		
		int p=1;
		int tot=bit;
		while (tot){
			int tmp=min(p,tot);
			
			append_right(temp,kbit,tmp);
			append_or(kbit,kbit,temp);
			
			tot-=tmp;
			p*=2;
		}
		
		//append_print(kbit);
		append_or(ARR,kbit,ARR);
	}
}

void construct_instructions(int S, int N, int K, int Q) {
	s=S,n=N,k=K,q=Q;
	
	vector<bool> allflip(B,1);
	append_store(ALLFLIP,allflip);
	
	vector<bool> v(B,0);
	v[0]=1;
		
	append_store(ONE,v);	
	rep(x,0,k) v[x]=1;
	append_store(AF,v);
	
	
	if (s==0){
		const int ans=99;
		
		get_min(n,k,ans);
		
		append_move(0,ans);
	}
	else{
		const int temp1=96,temp2=97,temp3=98,ans=99;
		
		rep(x,0,n){
			//need to find a way to fill the minimum value with all 1s
			get_min(n,k,temp1);
			
			append_left(temp2,temp1,x*k);
			append_or(ans,ans,temp2); //added to value to sorted list
			
			if (x==n-1) continue;
			
			rep(x,0,n){
				append_right(temp2,0,x*k);
				append_and(temp2,temp2,AF);
				append_xor(temp2,temp2,temp1); //this will be 0 if same
				
				//we force all differences into bit 1
				for (auto &it:{8,4,2,1}){
					append_right(temp3,temp2,it);
					append_or(temp2,temp2,temp3);
				}
				
				append_and(temp2,temp2,ONE); //equality holds if this bit is 0
				
				append_add(temp2,temp2,AF);
				append_and(temp2,temp2,AF);
				
				append_left(temp3,temp2,x*k);
				
				append_or(0,0,temp3);
				
				append_add(temp1,temp1,temp2);
			}
		}
		
		append_move(0,ans);
	}
}

Subtask #1
10.0 / 10.0

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

Subtask #2
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Wrong answer detected in grader

Subtask #3
12.0 / 12.0

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

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 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 5 ms 1032 KB Output is correct
2 Correct 3 ms 780 KB Output is correct

Subtask #6
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1032 KB Output is correct
2 Correct 3 ms 780 KB Output is correct
3 Incorrect 1 ms 628 KB Wrong answer detected in grader
4 Halted 0 ms 0 KB -