oj.uz

Submission #1075683

# Submission time Handle Problem Language Result Execution time Memory
1075683 2024-08-26T08:34:38 Z mickey080929 Bit Shift Registers (IOI21_registers) C++17
100 / 100
 3 ms 860 KB 
#include "registers.h"
#include <bits/stdc++.h>

using namespace std;

void append_move(int t, int y);
void append_store(int t, vector<bool> b);
void append_and(int t, int x, int y);
void append_or(int t, int x, int y);
void append_xor(int t, int x, int y);
void append_not(int t, int x);
void append_left(int t, int x, int p);
void append_right(int t, int x, int p);
void append_add(int t, int x, int y);
void append_print(int t);

static const int m = 100;
static const int b = 2000;

void cmp_and_swap(vector<int> u, vector<int> v, int k) {
	append_right(1, 0, u[0]*k);
	append_right(2, 0, v[0]*k);
	vector<bool> arr(b, 0);
	for (auto &x : u) {
		for (int i=(x-u[0])*k; i<(x-u[0]+1)*k; i++) {
			arr[i] = 1;
		}
	}
	append_store(3, arr);
	append_and(1, 1, 3);
	append_and(2, 2, 3);
	append_xor(4, 2, 3);
	append_add(5, 1, 4);
	append_right(5, 5, k);
	append_and(5, 3, 5);
	append_xor(5, 3, 5);
	fill(arr.begin(), arr.end(), 0);
	for (auto &x : u) {
		arr[(x-u[0]) * k] = 1;
	}
	append_store(6, arr);
	append_add(5, 5, 6);
	append_and(5, 3, 5);
	append_xor(6, 1, 2);
	append_and(6, 6, 5);
	append_left(7, 6, u[0] * k);
	append_xor(0, 0, 7);
	append_left(7, 6, v[0] * k);
	append_xor(0, 0, 7);
}

void construct_instructions(int s, int n, int k, int q) {
	if (s == 0) {
		for (int i=0; (1<<i)<n; i++) {
			vector<int> u, v;
			for (int j=1; (2*j-1)*(1<<i)<n; j++) {
				u.push_back((2*j-2)*(1<<i));
				v.push_back((2*j-1)*(1<<i));
			}
			cmp_and_swap(u, v, k);
		}
	}
	else {
		for (int i=0; i<n; i++) {
			if (i % 2 == 0) {
				vector<int> u, v;
				for (int j=0; j+1<n; j+=2) {
					u.push_back(j);
					v.push_back(j+1);
				}
				cmp_and_swap(u, v, k);
			}
			else {
				vector<int> u, v;
				for (int j=1; j+1<n; j+=2) {
					u.push_back(j);
					v.push_back(j+1);
				}
				cmp_and_swap(u, v, k);
			}
		}
	}
}

Subtask #1
10.0 / 10.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
12.0 / 12.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 1 ms 348 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 436 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #6
29.0 / 29.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 2 ms 856 KB Output is correct
4 Correct 3 ms 856 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 2 ms 860 KB Output is correct