oj.uz

Submission #796655

# Submission time Handle Problem Language Result Execution time Memory
796655 2023-07-28T15:22:47 Z caganyanmaz Bit Shift Registers (IOI21_registers) C++17
0 / 100
 1 ms 340 KB 
#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 j = i; j < b; j += k)
        {
                mask[j] = true;
        }
        return mask;
}
constexpr static int MXLOG = 10;

void fill_right(int i, int c, int tmp)
{
        for (int j = 0; j < MXLOG; j++)
        {
                if (c&(1<<j))
                {
                        append_right(tmp, i, 1<<j);
                        append_or(i, i, tmp);
                }
        }
}

void fill_left(int i, int c, int tmp)
{
        for (int j = 0; j < MXLOG; j++)
        {
                if (c&(1<<j))
                {
                        append_left(tmp, i, 1<<j);
                        append_or(i, i, tmp);
                }
        }
}

void subtask4()
{
        int l = k;
        while (l)
        {
                append_move(5, 0);
                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(0, 1, 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;
        cout << s <<" " << n << " " << k << " " << q <<"\n";
        if (s == 0 && n == 2 && k <= 2)
                subtask2();
        else if (s == 0)
                subtask4();
}

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Possible tampering with the output
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Possible tampering with the output
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Possible tampering with the output
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Possible tampering with the output
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Possible tampering with the output
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Possible tampering with the output
2 Halted 0 ms 0 KB -