oj.uz

Submission #1079823

# Submission time Handle Problem Language Result Execution time Memory
1079823 2024-08-29T02:09:50 Z GusterGoose27 Bit Shift Registers (IOI21_registers) C++17
0 / 100
 2 ms 348 KB 
#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_left(t, x, p);
	return t;
}

int make_right(int x, int p) {
	int t = get();
	append_right(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 u = 0; u < B; u += k) {
				for (int j = 0; j < B-(1<<i); j++) spec[u+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 make_move(x);
}

int make_min(int x, int y, bool care) { // also free x and y
	append_print(x);
	append_print(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);
	append_print(ans);
	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_right(u, k<<b);
		u = make_min(u, v, b>0);
	}
	append_move(0, u);
}

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Incorrect min value
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Incorrect min value
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 344 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 348 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 348 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -