Submission #1079791

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079791		GusterGoose27	Bit Shift Registers (IOI21_registers)	C++17	0 / 100	1 ms	348 KiB

registers

#include "registers.h"

#include <bits/stdc++.h>

using namespace std;

const int B = 2000;
vector<bool> spec;
set<int> avail;
int n, k;

int get() {
	assert(!avail.empty());
	int v = *avail.begin();
	avail.erase(v);
	return v;
}

void kill(int v) {
	avail.insert(v);
}

int make_move(int y) {
	int t = get();
	append_move(t, y);
	return t;
}

int make_store(vector<bool> v) {
	int t = get();
	append_store(t, v);
	return t;
}

int make_and(int x, int y) {
	int t = get();
	append_and(t, x, y);
	return t;
}

int make_or(int x, int y) {
	int t = get();
	append_or(t, x, y);
	return t;
}

int make_xor(int x, int y) {
	int t = get();
	append_xor(t, x, y);
	return t;
}

int make_not(int x) {
	int t = get();
	append_not(t, x);
	return t;
}

int make_left(int x, int p) {
	int t = get();
	append_and(t, x, p);
	return t;
}

int make_right(int x, int p) {
	int t = get();
	append_and(t, x, p);
	return t;
}

int make_add(int x, int y) {
	int t = get();
	append_add(t, x, y);
	return t;
}

int prefix_spread(int x, bool care) {
	for (int i = 0; (1<<i) < k; i++) {
		int y = make_right(x, (1<<i));
		if (care) {
			spec.assign(B, 0);
			for (int i = 0; i < B; i += k) {
				for (int j = (1<<i); j < B; j++) spec[i+j] = 1;
			}
			int tp = make_store(spec);
			int y2 = make_and(y, tp); kill(y); kill(tp);
			y = y2;
		}
		int v = make_or(x, y); kill(x); kill(y);
		x = v;
	}
	return x;
}

int make_min(int x, int y, bool care) { // also free x and y
	int nx = make_not(x);
	int ny = make_not(y);
	int u = make_and(x, ny);
	int v = make_and(y, nx);
	kill(nx); kill(ny);
	int yp = prefix_spread(v, care); kill(v);
	int nyp = make_not(yp); kill(yp);
	int u3 = make_and(u, nyp); kill(u);
	int u2 = prefix_spread(u3, care); kill(u3);
	int xy = make_xor(x, y);
	int xy2 = make_and(u2, xy); kill(xy); kill(u2);
	int ans = make_xor(x, xy2); kill(x); kill(y); kill(xy2);
	return ans;
}

void construct_instructions(int s, int N, int K, int q) {
	n = N; k = K;
	assert(s == 0);
	int u = 0;
	for (int i = 1; i < 100; i++) avail.insert(i);
	for (int b = 0; (1<<b)<n; b++) {
		int v = make_left(u, k<<b);
		u = make_min(u, v, b>0);
	}
}

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