oj.uz

Submission #607769

# Submission time Handle Problem Language Result Execution time Memory
607769 2022-07-27T03:42:33 Z KoD Bit Shift Registers (IOI21_registers) C++17
47 / 100
 1 ms 340 KB 
#include "registers.h"
#include <bits/stdc++.h>

using std::array;
using std::pair;
using std::tuple;
using std::vector;

constexpr int M = 100;
constexpr int B = 2000;

namespace ops {

bool locked[B];
bool vacant[B];

void init() {
    locked[0] = true;
    for (int i = 1; i < M; ++i) {
        vacant[i] = true;
    }
}

void lock(const int r) {
    assert(!locked[r]);
    assert(!vacant[r]);
    locked[r] = true;
}

void dump(const int r) {
    assert(!locked[r]);
    assert(!vacant[r]);
    vacant[r] = true;
}

void dump_all() {
    for (int i = 0; i < M; ++i) {
        if (!locked[i] and !vacant[i]) {
            dump(i);
        }
    }
}

int get_free() {
    int r = 0;
    while (r < M and !vacant[r]) {
        r += 1;
    }
    assert(r != M);
    vacant[r] = false;
    return r;
}

int copy(const int from) {
    assert(0 <= from and from < M);
    const int t = get_free();
    append_move(t, from);
    return t;
}

void debug(const int x) {
    assert(0 <= x and x < M);
    append_print(x);
}

void copy_to(const int from, const int to) {
    assert(0 <= from and from < M);
    assert(0 <= to and to < M);
    append_move(to, from);
}

int create(const vector<bool>& v) {
    assert((int)v.size() == B);
    const int t = get_free();
    append_store(t, v);
    return t;
}

int AND(const int x, const int y) {
    assert(0 <= x and x < M);
    assert(0 <= y and y < M);
    const int t = get_free();
    append_and(t, x, y);
    return t;
}

int OR(const int x, const int y) {
    assert(0 <= x and x < M);
    assert(0 <= y and y < M);
    const int t = get_free();
    append_or(t, x, y);
    return t;
}

int XOR(const int x, const int y) {
    assert(0 <= x and x < M);
    assert(0 <= y and y < M);
    const int t = get_free();
    append_xor(t, x, y);
    return t;
}

int ADD(const int x, const int y) {
    assert(0 <= x and x < M);
    assert(0 <= y and y < M);
    const int t = get_free();
    append_add(t, x, y);
    return t;
}

int NOT(const int x) {
    assert(0 <= x and x < M);
    const int t = get_free();
    append_not(t, x);
    return t;
}

int LEFT(const int x, const int s) {
    assert(0 <= x and x < M);
    assert(0 <= s and s <= B);
    const int t = get_free();
    append_left(t, x, s);
    return t;
}

int RIGHT(const int x, const int s) {
    assert(0 <= x and x < M);
    assert(0 <= s and s <= B);
    const int t = get_free();
    append_right(t, x, s);
    return t;
}

}

void solve_minimum(const int N, const int K) {
    for (int d = 1; d < N; d *= 2) {
        vector<bool> X(B), Y(B), Z(B, true);
        for (int i = 0; i + d < N; i += 2 * d) {
            for (int j = i * K; j < (i + 1) * K; ++j) {
                X[j] = true;
                Y[j + d * K] = true;
                Z[j] = false;
                Z[j + d * K] = false;
            }
        }
        const int x = ops::AND(ops::create(X), 0);
        const int y = ops::RIGHT(ops::AND(ops::create(Y), 0), d * K);
        ops::debug(x);
        ops::debug(y);
        const int z = ops::create(Z);
        const int sum = ops::ADD(ops::NOT(x), y);
        const int swap = ops::RIGHT(sum, K);
        const int stay = ops::NOT(swap);
        const int small = ops::OR(ops::AND(swap, y), ops::AND(stay, x));
        const int large = ops::OR(ops::AND(swap, x), ops::AND(stay, y));
        ops::debug(swap);
        ops::debug(stay);
        ops::debug(small);
        ops::debug(large);
        ops::copy_to(ops::OR(ops::OR(small, ops::LEFT(large, d * K)), ops::AND(0, z)), 0);
        ops::dump_all();
    }
}

void solve_sort(const int N, const int K) {}

void construct_instructions(int Subtask, int N, int K, int) {
    ops::init();
    if (Subtask == 0) {
        solve_minimum(N, K);
    } else {
        solve_sort(N, K);
    }
}

Subtask #1
10.0 / 10.0

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

Subtask #2
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Wrong answer detected in grader
2 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Incorrect sorting
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Incorrect sorting
2 Halted 0 ms 0 KB -