Submission #805309

#	Time	Username	Problem	Language	Result	Execution time	Memory
805309		SamAnd	Bit Shift Registers (IOI21_registers)	C++17	46 / 100	2 ms	628 KiB

registers

#include "registers.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define m_p make_pair
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
const int M = 100, B = 2000;

int s, n, k, q;

void comp(int x, int y, int z)
{
    append_xor(M - 1, x, y);
    append_and(M - 3, M - 1, y);
    for (int i = 0; i < min(4, k - 1); ++i)
    {
        append_right(M - 2, M - 1, (1 << i));
        append_or(M - 1, M - 1, M - 2);
    }

    append_not(M - 1, M - 1);
    append_right(M - 1, M - 1, 1);

    append_and(z, M - 3, M - 1);
    for (int i = 0; i < min(4, k - 1); ++i)
    {
        append_right(M - 2, z, (1 << i));
        append_or(z, z, M - 2);
    }
    for (int i = 0; i < min(4, k - 1); ++i)
    {
        append_left(M - 2, z, (1 << i));
        append_or(z, z, M - 2);
    }
}

void construct_instructions(int SS, int NN, int KK, int QQ) {
    s = SS;
    n = NN;
    k = KK;
    q = QQ;

    vector<bool> v;
    for (int i = 0; i < k; ++i)
        v.push_back(1);
    for (int i = 0; i < B - k; ++i)
        v.push_back(0);
    append_store(1, v);

    if (s == 0)
    {
        append_and(2, 0, 1);
        for (int i = 1; i < n; ++i)
        {
            append_right(3, 0, i * k);
            append_and(3, 3, 1);
            comp(2, 3, 4);
            append_not(5, 4);
            append_and(3, 3, 5);
            append_and(2, 2, 4);
            append_or(2, 2, 3);
        }

        append_move(0, 2);
    }
    else
    {
        for (int i = 0; i < n; ++i)
        {
            append_right(2 + i, 0, i * k);
            append_and(2 + i, 2 + i, 1);
        }
        for (int i = 0; i < n; ++i)
        {
            for (int j = i + 1; j < n; ++j)
            {
                comp(2 + i, 2 + j, M - 4);
                append_not(M - 5, M - 4);
                append_not(M - 6, M - 4);
                append_not(M - 7, M - 5);

                append_and(M - 4, M - 4, 2 + i);
                append_and(M - 5, M - 5, 2 + j);

                append_and(M - 6, M - 6, 2 + i);
                append_and(M - 7, M - 7, 2 + j);

                append_or(2 + i, M - 4, M - 5);
                append_or(2 + j, M - 6, M - 7);
            }
        }
        append_xor(0, 0, 0);
        for (int i = 0; i < n; ++i)
        {
            append_left(2 + i, 2 + i, i * k);
            append_or(0, 0, 2 + i);
        }
    }
}

/*
1 2 10 4000
1 0
0 1
-1

1 10 10 4000
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0
-1
*/

• Subtask 1: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 0 / 25
• Subtask 5: 13 / 13
• Subtask 6: 0 / 29