Submission #597584

#	Time	Username	Problem	Language	Result	Execution time	Memory
597584		8e7	Bit Shift Registers (IOI21_registers)	C++17	47 / 100	1 ms	292 KiB

registers

//Challenge: Accepted
#include "registers.h"
#include <bits/stdc++.h>
using namespace std;
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#define ll long long
#define maxn 400005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const int M = 100;
const int B = 2000;

void chmin(int K) {
	append_not(2, 1);
	append_and(2, 2, 98);
	append_add(2, 2, 97);
	append_add(2, 2, 0);
	append_print(2);
	append_right(3, 2, K);
	append_and(3, 3, 97);
	append_print(3);
	{
		int tmp = K;
		int i = 0;
		while (tmp) {
			if (tmp <= (1<<i)) {
				append_left(4, 3, tmp);
				append_or(3, 3, 4);
				tmp = 0;
			} else {
				append_left(4, 3, (1<<i));
				append_or(3, 3, 4);
				tmp -= 1<<i;
			}
			i++;
		}
	}
	append_print(3);
	append_not(4, 3);
	append_and(8, 1, 4); 
	append_and(9, 0, 3);
	append_add(0, 8, 9);
}
void solvemin(int N, int K) {
	if (N == 1) return;
	append_right(1, 0, K * (N / 2) * 2);
	append_and(1, 1, 99);
	append_print(0);
	append_print(1);
	chmin(K);
	//append_print(0);
	//append_print(1);
	solvemin((N + 1) / 2, K);
}
void construct_instructions(int tasktype, int N, int K, int q) {
	//special case for K=1
	if (K == 1) {
		vector<bool> odd(B, 0);
		for (int i = 1;i < B;i += 2) odd[i] = 1; 
		append_store(80, odd);
		append_not(81, 80);
		append_and(1, 0, 80);
		append_print(1);
		if (N % 2 == 0) append_left(1, 1, N - 1);
		else append_left(1, 1, N);
		append_or(0, 0, 1);
		append_and(0, 0, 81);
		append_print(0);
		K = 2;
		
	}
	
	//assuming K >=2
	vector<bool> st(B, 0), st2(B, 0), ones(B, 0), suf(B, 0);
	for (int j = 0;j < N;j += 2) {
		for (int i = 0;i < K;i++) {
			st[j*K + i] = 1, st2[j*K+i] = 1;	
		}
		ones[j*K] = 1;
		st2[(j+1)*K] = 1;
	}
	for (int i = N*K;i < B;i++) st[i] = 1, st2[i] = 1, suf[i] = 1;
	append_store(96, suf);
	append_or(0, 0, 96);
	append_store(99, st);
	append_store(98, st2);
	append_store(97, ones);
	if (tasktype == 0) {
		append_right(1, 0, K);
		append_and(0, 0, 99);
		append_and(1, 1, 99);	
		append_print(0);
		append_print(1);
		chmin(K);	
		solvemin((N+1) / 2, K);
		append_print(0);
		append_print(1);
	}	
}
/*
0 4 3 1000
1 3 4 2
 
*/

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