oj.uz

Submission #834580

# Submission time Handle Problem Language Result Execution time Memory
834580 2023-08-22T15:30:14 Z becaido Bit Shift Registers (IOI21_registers) C++17
100 / 100
 2 ms 596 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
#include "registers.h"
using namespace std;

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for(int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const int B = 2000;

void construct_instructions(int s, int n, int k, int q) {
    if (s == 0) {
        vector<bool> mask(B), one(B);
        if (n != 1 << __lg(n)) {
            FOR (i, n * k, B - 1) mask[i] = 1;
            append_store(50, mask);
            append_or(0, 0, 50);
        }
        n = 1 << (__lg(n - 1) + 1);
        if (k == 1) {
            for (int len = n >> 1; len >= 1; len >>= 1) {
                append_right(1, 0, len * k);
                append_and(0, 0, 1);
            }
            return;
        }
        for (int len = 2; len <= n; len <<= 1) {
            fill(mask.begin(), mask.end(), 0);
            fill(one.begin(), one.end(), 0);
            for (int i = 0; i < n; i += len) {
                one[i * k] = 1;
                FOR (j, 0, k - 1) mask[i * k + j] = 1;
            }
            append_store(50, mask);
            append_store(51, one);
            append_right(1, 0, len * k / 2);
            append_and(0, 0, 50);
            append_and(1, 1, 50);
            append_not(2, 1);
            for (int i = 0; i < n; i += len) mask[(i + 1) * k] = 1;
            append_store(52, mask);
            append_and(2, 2, 52);
            append_add(2, 2, 51);
            append_add(2, 2, 0);
            append_right(2, 2, k);
            append_and(2, 2, 51);
            append_not(2, 2);
            append_and(2, 2, 50);
            append_add(2, 2, 51);
            append_not(3, 2);
            append_and(0, 0, 2);
            append_and(1, 1, 3);
            append_or(0, 0, 1);
        }
        return;
    }

    vector<bool> mask[2], one[2], mid[2], mask2[2];
    mask[0] = mask[1] = one[0] = one[1] = mid[0] = mid[1] = mask2[0] = mask2[1] = vector<bool>(B);
    FOR (f, 0, 1) {
        int m = (n - f) / 2;
        fill(mid[f].begin(), mid[f].end(), 1);
        FOR (i, 0, m - 1) {
            one[f][2 * i * k] = mask2[f][(2 * i + 1) * k] = 1;
            FOR (j, 0, k - 1) {
                mask[f][2 * i * k + j] = mask2[f][2 * i * k + j] = 1;
                mid[f][(2 * i + f) * k + j] = mid[f][(2 * i + f + 1) * k + j] = 0;
            }
        }
    }
    append_store(50, mask[0]);
    append_store(51, mask[1]);
    append_store(52, one[0]);
    append_store(53, one[1]);
    append_store(54, mid[0]);
    append_store(55, mid[1]);
    append_store(56, mask2[0]);
    append_store(57, mask2[1]);
    FOR (t, 0, n - 1) {
        int f = t & 1, m = (n - f) / 2;
        if (m == 0) continue;
        append_right(1, 0, f * k);
        append_right(2, 0, (f + 1) * k);
        append_and(1, 1, 50 + f);
        append_and(2, 2, 50 + f);
        if (k == 1) {
            append_and(3, 1, 2);
            append_xor(2, 1, 2);
            append_xor(1, 2, 3);
            append_left(3, 3, f * k);
            append_left(1, 1, (f + 1) * k);
            append_and(0, 0, 54 + f);
            append_or(0, 0, 1);
            append_or(0, 0, 3);
            continue;
        }
        append_not(3, 2);
        append_and(3, 3, 56 + f);
        append_add(3, 3, 52 + f);
        append_add(3, 3, 1);
        append_right(3, 3, k);
        append_and(3, 3, 52 + f);
        append_not(3, 3);
        append_and(3, 3, 50 + f);
        append_add(3, 3, 52 + f);
        append_not(4, 3);
        append_and(3, 3, 1);
        append_and(4, 4, 2);
        append_or(3, 3, 4);
        append_xor(2, 1, 2);
        append_xor(1, 2, 3);
        append_left(3, 3, f * k);
        append_left(1, 1, (f + 1) * k);
        append_and(0, 0, 54 + f);
        append_or(0, 0, 1);
        append_or(0, 0, 3);
    }
}

Subtask #1
10.0 / 10.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
25.0 / 25.0

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

Subtask #5
13.0 / 13.0

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

Subtask #6
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct