oj.uz

Submission #994810

# Submission time Handle Problem Language Result Execution time Memory
994810 2024-06-08T06:29:35 Z 박영우(#10916) Bit Shift Registers (IOI21_registers) C++17
89 / 100
 1 ms 768 KB 
#include "registers.h"
#include <bits/stdc++.h>
using namespace std;

int S, N, K;

#define B 2000

#define CF1 1
#define CF2 2
#define C01 3
#define C10 4
#define C11 5
#define CANS 6
#define C1 7
#define C0 8
#define CM 9
#define CB 10

#define LA 50
#define LB 51
#define LF 52
#define LFR 53
#define LS 54
#define LN 56
#define LMN 57
#define LMX 58
#define LX 59
#define LO 60

vector<int> movek;

void make_filter() { // 13 operations
	if (K > 1) {
		append_xor(LF, CF2, LA);
		append_add(LF, LF, C1);
		append_add(LF, LF, LB);
		append_and(LF, LF, CF1);

		for (auto v : movek) { //8 operations
			append_right(LS, LF, v);
			append_or(LF, LS, LF);
		}
	}
	else {
		append_xor(LN, LB, C10);
		append_and(LF, LA, LN);
	}
	append_xor(LFR, C10, LF);
}

void construct_instructions(int s, int n, int k, int q) {
	S = s;
	N = n;
	K = k;
	vector<bool> v1(B), v2(B), v3(B), v4(B);
	int i;
	for (i = K; i < B; i += 2 * K) v1[i] = true;
	for (i = 0; i < B; i++) {
		if ((i / K) & 1) v2[i] = true;
		else v3[i] = true;
	}
	append_store(CF1, v1);
	append_store(C01, v2);
	append_store(C10, v3);
	for (i = K; i < B; i += 2 * K) v3[i] = true;
	append_store(CF2, v3);
	v4[0] = true;
	append_store(C1, v4);

	vector<bool> v5(K * N, true);
	v5.resize(B);
	append_store(C11, v5);

	int v = 1;
	int sum = 0;
	K++;
	while (sum < K) {
		v = min(v, K - sum);
		movek.push_back(v);
		sum += v;
		v *= 2;
	}
	K--;

	if (!s) {
		vector<bool> v6(B);
		for (i = 0; i < K; i++) v6[i] = 1;
		append_store(CANS, v6);

		int nn = 1;
		while (nn < N) nn <<= 1;
		vector<bool> app(B);
		for (i = N * K; i < nn * K; i++) app[i] = 1;
		append_store(LA, app);
		append_or(LA, 0, LA);

		N = nn;
		append_and(LB, LA, C01);
		append_and(LA, LA, C10);
		append_right(LB, LB, K);
		append_print(C01);
		while (N > 1) {
			append_print(LA);
			append_print(LB);
			make_filter();
			append_print(LF);
			append_and(LA, LA, LFR);
			append_and(LB, LB, LF);
			append_add(LA, LA, LB);

			append_right(LB, LA, K * N / 2);
			N /= 2;
		}
		append_and(0, LA, CANS);
	}
	else {
		vector<bool> v6(B);
		for (i = 0; i < N * K; i++) v6[i] = 1;
		append_store(CANS, v6);

		int nn = N;
		nn = (N + 1) >> 1;
		nn <<= 1;
		vector<bool> app(B);
		for (i = N * K; i < nn * K; i++) app[i] = 1;
		N = nn;
		append_store(LA, app);
		append_or(LA, 0, LA);

		vector<bool> v7(B);
		for (i = K; i < (N - 1) * K; i++) v7[i] = 1;
		append_store(CM, v7);

		vector<bool> v8(B);
		for (i = 0; i < K; i++) v8[i] = 1;
		for (i = (N - 1) * K; i < N * K; i++) v8[i] = 1;
		append_store(CB, v8);

		int t;
		for (t = 1; t <= N; t++) {
			append_print(LA);
			if (t & 1) {
				append_and(LB, LA, C01);
				append_and(LA, LA, C10);
				append_right(LB, LB, K);

				append_print(LA);
				append_print(LB);
				make_filter();
				append_print(LF);
				append_print(LFR);

				append_and(LX, LA, LFR);
				append_and(LMN, LB, LF);
				append_add(LMN, LMN, LX);
				append_and(LX, LB, LFR);
				append_and(LMX, LA, LF);
				append_add(LMX, LMX, LX);

				append_print(LMN);
				append_print(LMX);

				append_left(LA, LMX, K);
				append_print(LA);
				append_add(LA, LA, LMN);
				append_print(LA);

			}
			else {
				append_and(LO, LA, CB);

				append_and(LA, CM, LA);
				append_right(LA, LA, K);

				append_and(LB, LA, C01);
				append_and(LA, LA, C10);
				append_right(LB, LB, K);

				append_print(LA);
				append_print(LB);
				make_filter();
				append_print(LF);
				append_print(LFR);

				append_and(LX, LA, LFR);
				append_and(LMN, LB, LF);
				append_add(LMN, LMN, LX);
				append_and(LX, LB, LFR);
				append_and(LMX, LA, LF);
				append_add(LMX, LMX, LX);
				append_left(LA, LMX, K);
				append_add(LA, LA, LMN);

				append_left(LA, LA, K);
				append_add(LA, LA, LO);
			}
		}
		append_and(0, LA, CANS);
	}
}

Subtask #1
10.0 / 10.0

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

Subtask #2
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Wrong answer detected in grader
2 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

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

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #5
13.0 / 13.0

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

Subtask #6
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 768 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct