Submission #597962

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

registers

//Challenge: Accepted
#include "registers.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
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;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#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, int sw) {
	append_not(2, 1);
	append_and(2, 2, 98);
	append_add(2, 2, 97);
	append_add(2, 2, 0);
	append_right(3, 2, K);
	append_and(3, 3, 97);
	{
		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_not(4, 3);
	append_and(8, 1, 4); 
	append_and(9, 0, 3);
	if (sw) {
		append_and(10, 0, 4);
		append_and(11, 1, 3);
		append_add(1, 10, 11);
	}
	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, 0);
	solvemin((N + 1) / 2, K);
}

void sortlayer(int N, int K, vector<int> sep) {
	append_print(0);
	if (sep.size() == N+1) return;
	
	vector<bool> se(B, 0);
	vector<int> nxt;
	int dis = 0;
	for (int i = 1;i < sep.size();i++) {
		if (sep[i] - sep[i-1] > 1) {
			dis = max(dis, sep[i] - sep[i-1] - 1);
			int p = (sep[i-1] + sep[i]) / 2;
			for (int j = p;j < sep[i];j++) {
				for (int e = 0;e < 2*K;e++) se[j*2*K + e] = 1;	
			}
			nxt.push_back(p);
		}
	}
	append_store(51, se);
	append_not(52, 51);
	append_print(52);
	append_or(1, 52, 0);	
	append_and(0, 52, 0);
	append_print(0);
	append_print(1);
	append_move(49, 69); //clear 49
	for (int i = 1;i <= dis;i++) {
		append_right(1, 1, 2*K);
		append_and(1, 1, 99);

		append_print(69);
		append_print(0);
		append_print(1);
		chmin(K, 1);
		append_print(0);
		append_print(1);
		append_and(2, 1, 50);
		append_left(2, 2, i * 2*K);	
		append_or(49, 49, 2);
	}	
	append_left(1, 1, 2*K*dis);	
	append_or(1, 1, 49);
	append_and(1, 1, 51);
	append_or(0, 0, 1);
	sep.insert(sep.end(), nxt.begin(), nxt.end());	
	sort(sep.begin(), sep.end());
	sortlayer(N, K, sep);
}
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 < 2*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++) suf[i] = 1;
	for (int i = 2*N*K;i < B;i++) st[i] = st2[i] = 1;
	if (N > 2) {
		append_store(96, suf);
		append_or(0, 0, 96);
	}
	append_store(99, st); //alternate K bits
	append_store(98, st2); //alternate K+1 1s, K-1 0s
	append_store(97, ones); //1 + 2K-1 0s

	append_right(1, 0, K);
	append_and(0, 0, 99);
	append_and(1, 1, 99);
	if (tasktype == 0) {
		append_print(0);
		append_print(1);
		chmin(K, 0);	
		solvemin((N+1) / 2, K);
		append_print(0);
		append_print(1);
	} else {
		vector<bool> fi(B, 0), tmp(B, 0);
		for (int i = 0;i < K;i++) fi[i] = 1;
		append_store(50, fi);
		int siz = (N+1) / 2;
		for (int i = 0;i < siz*2*K;i++) tmp[i] = 1;
		append_store(48, tmp);
		for (int i = 0;i < siz;i++) {
			if (i) {
				append_right(2, 1, (siz-1)* 2*K);
				append_and(2, 2, 50);
				append_left(1, 1, 2*K);
				append_or(1, 2, 1);
			}
			chmin(K, 1);
		}	
		append_and(0, 0, 48);	
		if (siz % 2) {
			append_right(2, 1, (siz-1)* 2*K);
			append_and(2, 2, 50);
			append_left(1, 1, 2*K);
			append_or(1, 2, 1);
		}
		append_left(1, 1, siz * 2 * K);
		append_or(0, 0, 1);
		vector<int> vec = {0, siz, N};
		sortlayer(N, K, vec);
		for (int i = 0;i < N;i++) {
			append_left(1, 0, B - (2*i*K + K));
			append_right(1, 1, B - K);
			append_left(1, 1, i*K);
			append_or(69, 1, 69);
		}
		append_move(0, 69);
	}
}
/*
0 4 3 1000
1 3 4 2
 
*/

Compilation message (stderr)

registers.cpp: In function 'void sortlayer(int, int, std::vector<int>)':
registers.cpp:70:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   70 |  if (sep.size() == N+1) return;
      |      ~~~~~~~~~~~^~~~~~
registers.cpp:75:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |  for (int i = 1;i < sep.size();i++) {
      |                 ~~^~~~~~~~~~~~

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