Submission #796702

#	Time	Username	Problem	Language	Result	Execution time	Memory
796702		caganyanmaz	Bit Shift Registers (IOI21_registers)	C++17	33 / 100	1 ms	340 KiB

registers

#include <bits/stdc++.h>
#define pb push_back
#include "registers.h"
using namespace std;

constexpr static int b = 2000;
int n, s, k, q;

void get_second(int t)
{
        append_left(t, t, b-2);
        append_right(t, t, b-1);
}

void _fix(int t)
{
        append_xor(3, t, 2);
        get_second(3);
        append_or(t, t, 3);
}

void subtask2()
{
        if (k == 2)
        {
                append_right(1, 0, 2);
                append_and(2, 0, 1);
                _fix(0);
                _fix(1);
                append_and(0, 0, 1);
        }
        else
        {
                append_right(1, 0, 1);
                append_and(0, 0, 1);
        }
}

vector<bool> big;
vector<bool> small;

void preprocess()
{
        big.pb(true);
        small.pb(true);
        for (int i = 1; i < b; i++)
        {
                big.pb(true);
                small.pb(false);
        }
}


// 3 ops
// to y: first 1000 bits on if i is not zero, all bits off if i 0
// to t: opposite
// NOTE: Assumed i doesn't have open bits after 1000
void set_zero(int i, int t, int y)
{
        append_store(t, big);
        append_add(t, i, t);
        append_right(t, t, b/2);
        append_not(y, t);
}


vector<bool> create_mask(int i)
{
        vector<bool> mask(b, false);
        for (int l = 0; l < n; l++)
        {
                mask[l*k+i] = true;
        }
        return mask;
}
constexpr static int MXLOG = 10;

void fill_right(int i, int c, int tmp)
{
        c++;
        while (c>1)
        {
                if (c&1)
                {
                        c--;
                        append_right(tmp, i, 1);
                        append_or(i, i, tmp);
                }
                else
                {
                        c>>=1;
                        append_right(tmp, i, c);
                        append_or(i, i, tmp);
                }
        }
}

void fill_left(int i, int c, int tmp)
{
        c++;
        while (c >1)
        {
                if (c&1)
                {
                        c--;
                        append_left(tmp, i, 1);
                        append_or(i, i, tmp);
                }
                else
                {
                        c>>=1;
                        append_left(tmp, i, c);
                        append_or(i, i, tmp);
                }
        }
}

void subtask4()
{
        int l = k;
        append_move(5, 0);
        while (l>1)
        {

                if (l&1)
                {
                        append_right(6, 5, 1);
                        append_or(5, 5, 6);
                        l--;
                }
                else
                {
                        l >>= 1;
                        append_right(6, 5, l);
                        append_or(5, 5, 6);
                }
        }
        append_not(5, 5);
        vector<bool> v = create_mask(0);
        append_store(6, v);
        append_and(6, 5, 6);
        set_zero(6, 7, 8);

        for (int i = k-1; i >= 0; i--)
        {
                vector<bool> v = create_mask(i);
                append_store(1, v);
                append_and(1, 0, 1);
                fill_right(1, i, 2);
                fill_left(1, k-1-i, 2);
                // Filling on bits 1
                append_not(2, 1); // Opposite
                append_and(1, 0, 1); // The ones who have the bit on
                append_and(2, 0, 2); // The ones who have the bit off
                set_zero(2, 3, 4); // 3 if 2 is empty, 4 otherwise
                append_and(1, 1, 3);
                append_and(2, 2, 4);
                append_or(0, 1, 2);
        }
        for (int i = 0; i < 7; i++)
        {
                append_right(1, 0, k * (1<<i));
                append_or(0, 0, 1);
        }
        append_and(0, 0, 7);
}

void construct_instructions(int ss, int nn, int kk, int qq)
{
        preprocess();
        s =ss, n = nn, k = kk, q = qq;
        if (s == 0 && n == 2 && k <= 2)
                subtask2();
        else if (s == 0)
                subtask4();
}

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