oj.uz

Submission #471818

# Submission time Handle Problem Language Result Execution time Memory
471818 2021-09-11T03:52:00 Z SHZhang Bit Shift Registers (IOI21_registers) C++17
100 / 100
 2 ms 620 KB 
#include "registers.h"
#include <vector>

using namespace std;

int n, k, q;

void work_min(int cnt, int width)
{
    if (cnt == 1) return;
    vector<bool> mask(2000), mask2(2000), highbits(2000);
    for (int i = 0; i < cnt * width; i++) {
        if ((i / width) % 2 == 0) mask[i] = true;
        else mask2[i] = true;
        if ((i + 1) % (width * 2) == 0) highbits[i] = true;
        //if (i % (width * 2) >= width && !highbits[i]) midhighbits[i] = true;
    }
    append_store(50, mask);
    append_store(51, highbits);
    append_store(52, mask2);
    append_and(3, 0, 52);
    append_right(3, 3, width);
    append_not(1, 3);
    append_xor(1, 1, 51);
    append_and(0, 0, 50);
    append_add(2, 0, 1);
    append_xor(2, 2, 51);
    append_and(2, 2, 52);
    append_right(2, 2, width);
    append_and(4, 0, 2);
    append_xor(2, 2, 50);
    append_and(5, 3, 2);
    append_or(0, 4, 5);
    append_print(0);
    work_min(cnt / 2, width * 2);
}

void solve_min()
{
    if (n == 2) {
        work_min(2, k);
    } else {
        vector<bool> extra_bits(2000);
        for (int i = n; i < 128; i++) {
            for (int j = 0; j < k; j++) {
                extra_bits[i * k + j] = true;
            }
        }
        append_store(1, extra_bits);
        append_or(0, 0, 1);
        work_min(128, k);
    }
}

void work_even()
{
    append_move(10, 0);
    append_and(3, 0, 52);
    append_right(3, 3, k);
    append_not(1, 3);
    append_xor(1, 1, 51);
    append_and(0, 0, 50);
    append_add(2, 0, 1);
    append_xor(2, 2, 51);
    append_and(2, 2, 52);

    //append_print(2);

    append_right(4, 2, k);
    append_or(5, 2, 4);
    append_and(6, 5, 10);

    //append_print(5);
    append_not(5, 5);
    //append_print(5);
    append_left(7, 0, k);
    append_or(7, 3, 7);
    append_and(7, 5, 7);

    //append_print(6);
    //append_print(7);

    append_or(0, 6, 7);
}

void work_odd()
{
    append_and(20, 0, 53);
    append_xor(0, 0, 20);
    append_right(0, 0, k);
    work_even();
    append_left(0, 0, k);
    append_or(0, 0, 20);
}

void solve_sort()
{
    bool isodd = (n % 2);
    if (isodd) n++;
    vector<bool> mask(2000), mask2(2000), highbits(2000), endvals(2000);
    for (int i = 0; i < n * k; i++) {
        if ((i / k) % 2 == 0) mask[i] = true;
        else mask2[i] = true;
        if ((i + 1) % (2 * k) == 0) highbits[i] = true;
        if ((i / k) == 0 || (i / k) == n - 1) endvals[i] = true;
    }
    append_store(50, mask);
    append_store(51, highbits);
    append_store(52, mask2);
    append_store(53, endvals);
    //work_even();
    for (int i = 1; i <= n; i++) {
        work_even();
        append_print(0);
        work_odd();
        append_print(0);
    }
    if (isodd) append_right(0, 0, k);
}

void construct_instructions(int s, int N, int K, int Q)
{
    n = N; k = K; q = Q;
    if (s == 0) {
        solve_min();
    } else {
        solve_sort();
    }
}

Subtask #1
10.0 / 10.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
12.0 / 12.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

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 2 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 204 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 204 KB Output is correct
3 Correct 2 ms 620 KB Output is correct
4 Correct 2 ms 620 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct