oj.uz

Submission #819395

# Submission time Handle Problem Language Result Execution time Memory
819395 2023-08-10T10:15:19 Z HamletPetrosyan Bit Shift Registers (IOI21_registers) C++17
58 / 100
 1 ms 340 KB 
#include "registers.h"
#include <bits/stdc++.h>
using namespace std;

const int M = 100, B = 2000;

// 99 - zero
// 98 - pair 2nd
// 97 - pair 1st
// 96 - 0 cleaner
// 95 - ones for the pairs
// 94 - checker ones

// 1 - pair 1st
// 2 - pair 2nd

// 3 - not pair 2nd (xor with ones)
// 4 - 3 + ones
// 5 - 4 + 1

// 6 - 5 & 94
// 7 - 6 >> k
// 8 - 7 + 97
// 9 - 8 & 97
// 10 - 9 ^ 97

// 11 - 1 & 9
// 12 - 2 & 10

void get_min(int n, int k){
	int hn = n;
	vector<bool> v98(B), v97(B), v96(B), v95(B), v94(B), usd(n);
	while(hn - 1){	
		for(int i = 0; i < B; i++){
			v98[i] = v97[i] = v96[i] = v95[i] = v94[i] = 0;
		}

		bool cnt = 0;
		int g = B, cc = 0;
		for(int i = 0; i < n; i++){
			if(usd[i]) continue;
			cc++;
			if(cnt){
				for(int j = i * k; j < (i + 1) * k; j++) v98[j] = 1;
				usd[i] = 1;
				g = min(g, i * k);
			}
			else if(cc == hn){
				for(int j = i * k; j < (i + 1) * k; j++) v96[j] = 1;
			}
			else {
				for(int j = i * k; j < (i + 1) * k; j++) v97[j] = 1;
				v95[i * k] = 1;
				v94[(i + 1) * k] = 1;
			}
			cnt = !cnt;
		}
		hn = (hn + 1) / 2;

		append_store(98, v98);														// <-------- 1
//		append_print(98);
		append_store(97, v97);														// <-------- 2
//		append_print(97);
//		append_store(96, v96); 
		append_store(95, v95);														// <-------- 3
//		append_print(95);
		append_store(94, v94);														// <-------- 4
//		append_print(94);

		append_and(1, 0, 97);														// <-------- 5
		append_and(2, 0, 98);														// <-------- 6
		append_right(2, 2, g);														// <-------- 7
//		append_and(0, 0, 96);
		append_xor(0, 0, 1);														// <-------- 8
		
		append_xor(3, 2, 97);														// <-------- 9
		append_add(4, 3, 95);														// <-------- 10
		append_add(5, 4, 1);														// <-------- 11

		append_and(6, 5, 94);														// <-------- 12
		append_right(7, 6, k);														// <-------- 13
		append_add(8, 7, 97);														// <-------- 14
		append_and(9, 8, 97);														// <-------- 15
		append_xor(10, 9, 97);														// <-------- 16

		append_and(11, 1, 9);														// <-------- 17
		append_and(12, 2, 10);														// <-------- 18

		append_add(0, 0, 11);														// <-------- 19
		append_add(0, 0, 12);														// <-------- 20
//		append_print(0);
	}
}

void get_sorted(int n, int k){
	vector<bool> stv(k);
}

void construct_instructions(int s, int n, int k, int q) {
	if(s) get_sorted(n, k);
	else get_min(n, k);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Incorrect sorting
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Incorrect sorting
2 Halted 0 ms 0 KB -