oj.uz

답안 #607898

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
607898 2022-07-27T04:38:32 Z KoD 레지스터 (IOI21_registers) C++17
100 / 100
 1 ms 468 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);
        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));
        if (N == 2) {
            ops::copy_to(ops::OR(small, ops::LEFT(large, d * K)), 0);
        } else {
            ops::copy_to(ops::OR(ops::OR(small, ops::LEFT(large, d * K)), ops::AND(0, ops::create(Z))), 0);
        }
        ops::dump_all();
    }
}

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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 340 KB Output is correct
6 Correct 1 ms 304 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #6
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct