oj.uz

답안 #1060226

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1060226 2024-08-15T11:42:10 Z vjudge1 레지스터 (IOI21_registers) C++17
89 / 100
 2 ms 764 KB 
#include "registers.h"

#include <bits/stdc++.h>

using namespace std;

using ii = pair<int, int>;

set<int> Liberi;

const int B = 2000;

int n, k;
int BM_sel0, BM_sel1, BM_sel12, BM_k1, BM_plus1, BM_sufix1, BM_sufix2, BM_primul;

void get_bm(int tip);
void free(int x);
int xor0(int a, int b);
int and0(int a, int b);
int or0(int a, int b);
int not0(int a);
int plus0(int a, int b);
int left(int a, int nr);
int right(int a, int nr);

int dif(int b, int c) {
    ///4 operatii
    int x1 = xor0(BM_k1, c);
    int minc = plus0(x1, BM_plus1);
    free(x1);
    int re = and0(plus0(b, minc), BM_k1); /// (b + not C + 1) & BM_k1
    free(minc);
    return re;
}
int dif2(int bplus, int c) {
    ///4 operatii
    int x1 = xor0(BM_k1, c);
    int v0 = plus0(bplus, x1);
    int re = and0(v0, BM_k1); /// (b + not C + 1) & BM_k1
    free(x1);
    free(v0);
    return re;
}


int min0(int b, int c) {
    int bpl = plus0(b, BM_plus1);
    int d = dif2(bpl, c); /// b - c, 0 / 1,  ... 

    int d0 = d;
    d = and0(d, BM_sel12);
    int len = 1;
    while(len <= k) {
        if(2 * len <= k + 1) {
            int d1 = or0(d, right(d, len));
            free(d);
            d = d1;
            len *= 2;
        } else {
            int d1 = or0(d, right(d, k + 1 - len));
            free(d);
            d = d1;
            break;
        }
    }
    int e = and0(d0, not0(d)); /// max(b - c, 0), 0 ...
    free(d0);
    free(d);
    int re = dif2(bpl, e);
    free(bpl);
    free(e);
    return re;
}

int bubble0(int b, int c) {
    ///will return min(b1, c1) max(b1, c1) ,....
    ///basically a round of bubble sort
    int bpl = plus0(b, BM_plus1);
    int d = dif2(bpl, c); /// b - c, 0 / 1,  ... 

    int d0 = d;
    d = and0(d, BM_sel12);
    int len = 1;
    while(len <= k) {
        if(2 * len <= k + 1) {
            int rightdlen = right(d, len);
            int d1 = or0(d, rightdlen);
            free(rightdlen);
            free(d);
            d = d1;
            len *= 2;
        } else {
            int rightdk = right(d, k + 1 - len);
            int d1 = or0(d, rightdk);
            free(rightdk);
            free(d);
            d = d1;
            break;
        }
    }
    int not0d = not0(d);
    int e = and0(d0, not0d); /// max(b - c, 0), 0 ...
    free(not0d);
    free(d0);
    free(d);

    int sum = plus0(c, e);
    int re1 = left(sum, k);
    free(sum);
    int re0 = dif2(bpl, e);
    free(bpl);
    free(e);
    int re = plus0(re0, re1);
    free(re0);
    free(re1);
    return re;
}


void construct_instructions(int s, int n0, int k0, int q) {
    for(int i = 1; i <= 100; ++i) free(i);
    n = n0; k = k0;
    get_bm(s);
    if(s == 0) {
        int orig = 0;
        int a = and0(BM_sel0, orig), b = right(and0(BM_sel1, orig), k);
        if(n & 1) {
            b = or0(b, BM_sufix2);
        }


        for(int step = 1; (1 << (step - 1)) < n; ++step) {
            int c = min0(a, b);
            append_print(c);
            if((1 << step) >= n) {
                append_move(0, c);
                return;
            }
            a = or0(c, BM_sufix1);
            b = right(a, (1 << step) * k);

            append_print(a);
            append_print(b);
        }
    } else  {
        int c = 0;
        append_print(0);
        auto bubso = [&](int root, int len) {
            int v0 = and0(BM_sel1, root);
            int a = and0(BM_sel0, root), b = right(v0, k);
            free(v0);
            if(len & 1) {
                int b2 = or0(b, BM_sufix2);
                free(b);
                b = b2;
            }
            int re = bubble0(a, b);
            free(a);
            free(b);
            return re;
        };
        auto fa_pare = [&]() {
            int v =  bubso(c, n);
            free(c);
            c = v;
        };
        auto fa_impare = [&]() {
            int a0 = and0(BM_primul, c);
            int r = right(c, k);
            int r2;

            r2 = bubso(r, n - 1);
            free(r);
            r = r2;

            r2 = left(r, k);
            free(r);
            r = r2;

            r2 = or0(r, a0);
            free(r);
            r = r2;

            free(a0);
            free(c);
            c = r;
        };
        for(int i = 0; i < n / 3 * 2; ++i) {
            fa_pare();
            fa_impare();
        }
        if(c)
            append_move(0, c);
        append_print(0);
    }
}

int get_reg() { 
    int v = *Liberi.begin();
    Liberi.erase(v);
    return v;
}

int store_bm(vector<bool> V) {
    int v = get_reg();
    append_store(v, V);
    return v;
}


void get_bm(int s) {
    vector<bool> V(B, false);
    for(int i = 0; i < n; ++i) {
        if(!(i & 1)) {
            for(int j = 0; j < k; ++j)
                V[i * k + j] = 1;
        }
    }
    BM_sel0 = store_bm(V); /// 11..1 00..0 11..1 etc
    V.assign(B, false);
    for(int i = 0; i < n; ++i) {
        if(i & 1) {
            for(int j = 0; j < k; ++j)
                V[i * k + j] = 1;
        }
    }
    BM_sel1 = store_bm(V);
    V.assign(B, false);
    for(int i = 0; i < n + 2; ++i) {
        if(i & 1) {
            for(int j = 0; j < k; ++j)
                V[i * k + j] = 1;
        }
    }
    BM_sel12 = store_bm(V);
    V.assign(B, false);
    for(int i = 0; i < n; ++i) {
        if(!(i & 1)) {
            for(int j = 0; j <= k; ++j)
                V[i * k + j] = 1;
        }
    }
    BM_k1 = store_bm(V);
    V.assign(B, false);
    for(int i = 0; i < n; ++i) {
        if(!(i & 1)) {
            V[i * k] = 1;
        }
    }
    BM_plus1 = store_bm(V);

    V.assign(B, false);
    for(int i = n; i * k < B; ++i) {
        if(!(i & 1)) {
            for(int j = 0; j < k; ++j)
                if(i * k + j < B)
                    V[i * k + j] = 1;
        }
    }
    BM_sufix1 = store_bm(V);

    V.assign(B, false);
    for(int i = n - 2; i * k < B; ++i) {
        if(!(i & 1)) {
            for(int j = 0; j < k; ++j)
                if(i * k + j < B)
                    V[i * k + j] = 1;
        }
    }
    BM_sufix2 = store_bm(V);
    if(s) {
        V.assign(B, false);
        for(int i = 0; i < k; ++i) V[i] = true;
        BM_primul = store_bm(V);
    }
}

void free(int x) { Liberi.insert(x); }

int xor0(int a, int b) {
    int v = get_reg();
    append_xor(v, a, b);
    return v;
}

int plus0(int a, int b) {
    int v = get_reg();
    append_add(v, a, b);
    return v;
}

int or0(int a, int b) {
    int v = get_reg();
    append_or(v, a, b);
    return v;
}

int and0(int a, int b) {
    int v = get_reg();
    append_and(v, a, b);
    return v;
}

int left(int a, int nr) {
    int v = get_reg();
    append_left(v, a, nr);
    return v;
}
int right(int a, int nr) {
    int v = get_reg();
    append_right(v, a, nr);
    return v;
}

int not0(int a) {
    int v = get_reg();
    append_not(v, a);
    return v;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB Wrong answer detected in grader
2 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

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

Subtask #4
25.0 / 25.0

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

Subtask #5
13.0 / 13.0

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

Subtask #6
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 764 KB Output is correct
4 Correct 1 ms 692 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct