oj.uz

Submission #466604

# Submission time Handle Problem Language Result Execution time Memory
466604 2021-08-19T18:18:32 Z alexxela12345 Bit Shift Registers (IOI21_registers) C++17
100 / 100
 7 ms 1448 KB 
#include "registers.h"
#include <bits/stdc++.h>
using namespace std;

const int B = 2000;
const int M = 100;

void solve0(int n, int k, int q) {
    append_print(0);
    // make n a power of 2
    {
        vector<bool> adding(B);
        bool was = 0;
        while (n & (n - 1)) {
            for (int i = n * k; i < (n + 1) * k; i++) {
                adding[i] = 1;
            }
            was = 1;
            n++;
        }
        if (was) {
            append_store(1, adding);
            append_xor(0, 0, 1);
        }
    }
    {
        // 8th cell is 1
        vector<bool> one(B);
        one[0] = 1;
        append_store(8, one);
    }
    for (int len = 1; len < n; len *= 2) {
        // what single iteration does:
        // for i in range(0, n, 2 * len):
        //     chkmin(a[i], a[i + len])
        // after all iterations a[0] is min(a)
        vector<bool> mask_ones(B);
        for (int i = 0; i < n; i += 2 * len) {
            mask_ones[k + i * k] = 1;
        }
        append_store(6, mask_ones);
        append_print(0);
        vector<bool> mask_odd(B), mask_even(B);
        for (int i = 0; i * 2 * len < n; i++) {
            for (int j = 0; j < k; j++) {
                mask_even[i * 2 * len * k + j] = 1;
                mask_odd[(2 * i + 1) * len * k + j] = 1;
            }
        }
        append_store(1, mask_even);
        append_store(2, mask_odd);
        append_and(3, 0, 1);
        append_and(4, 0, 2);
        append_right(4, 4, len * k);
        append_print(3);
        append_print(4);
        append_not(4, 4);
        append_add(5, 3, 4);
        append_add(5, 5, 6);
        append_not(4, 4);
        append_print(5);
        append_and(6, 6, 5);
        append_right(7, 6, k);
        append_not(7, 7);
        append_add(7, 7, 8);
        append_add(7, 7, 6);
        append_print(7);
        append_and(4, 4, 7);
        append_not(7, 7);
        append_and(3, 3, 7);
        append_print(3);
        append_print(4);
        append_xor(0, 3, 4);
    }
}

void solve1(int n, int k, int q) {
    // make n a power of 2
    {
        vector<bool> adding(B);
        bool was = 0;
        while (n & (n - 1)) {
            for (int i = n * k; i < (n + 1) * k; i++) {
                adding[i] = 1;
            }
            was = 1;
            n++;
        }
        if (was) {
            append_store(1, adding);
            append_xor(0, 0, 1);
        }
    }
    {
        // 8th cell is 1
        vector<bool> one(B);
        one[0] = 1;
        append_store(8, one);
    }
    auto SWAP = [&]() {
        const int len = 1;
        vector<bool> mask_ones(B);
        for (int i = 0; i < n; i += 2 * len) {
            mask_ones[k + i * k] = 1;
        }
        append_store(6, mask_ones);
        append_print(0);
        vector<bool> mask_odd(B), mask_even(B);
        for (int i = 0; i * 2 * len < n; i++) {
            for (int j = 0; j < k; j++) {
                mask_even[i * 2 * len * k + j] = 1;
                mask_odd[(2 * i + 1) * len * k + j] = 1;
            }
        }
        append_store(1, mask_even);
        append_store(2, mask_odd);
        append_and(3, 0, 1);
        append_and(4, 0, 2);
        append_right(4, 4, len * k);
        append_print(3);
        append_print(4);
        append_not(4, 4);
        append_add(5, 3, 4);
        append_add(5, 5, 6);
        append_not(4, 4);
        append_print(5);
        append_and(6, 6, 5);
        append_right(7, 6, k);
        append_not(7, 7);
        append_add(7, 7, 8);
        append_add(7, 7, 6);
        append_print(7);
        append_and(9, 4, 7);
        append_and(11, 3, 7);
        append_not(7, 7);
        append_and(10, 3, 7);
        append_and(12, 4, 7);
        append_xor(3, 9, 10);
        append_xor(4, 11, 12);
        append_print(3);
        append_print(4);
        append_left(4, 4, k);
        append_print(3);
        append_print(4);
        append_xor(0, 3, 4);
        append_print(0);
    };
    {
        vector<bool> first(B);
        fill(first.begin(), first.begin() + k, 1);
        append_store(M - 1, first);
        append_left(M - 2, M - 1, (n - 1) * k);
    }
    for (int it = 0; it < n; it++) {
        if (it % 2 == 0) {
            SWAP();
        } else {
            append_and(M - 3, M - 1, 0);
            append_right(0, 0, k);
            append_xor(0, 0, M - 2);
            SWAP();
            append_xor(0, 0, M - 2);
            append_left(0, 0, k);
            append_xor(0, 0, M - 3);
        }
    }
}

void construct_instructions(int s, int n, int k, int q) {
    if (s == 0) {
        solve0(n, k, q);
    } else {
        solve1(n, k, q);
    }
}

Subtask #1
10.0 / 10.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
25.0 / 25.0

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

Subtask #5
13.0 / 13.0

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

Subtask #6
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 7 ms 1448 KB Output is correct
4 Correct 6 ms 1448 KB Output is correct
5 Correct 7 ms 1396 KB Output is correct
6 Correct 4 ms 844 KB Output is correct
7 Correct 3 ms 844 KB Output is correct