Submission #1060130

# Submission time Handle Problem Language Result Execution time Memory
1060130 2024-08-15T10:50:30 Z vjudge1 Bit Shift Registers (IOI21_registers) C++17
47 / 100
1 ms 348 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;

void get_bm();
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,  ... 

    append_print(d);
    int d0 = d;
    d = and0(d, BM_sel12);
    int len = 1;
    append_print(d);
    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;
}


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();
    int orig = 0;
    int a = and0(BM_sel0, orig), b = right(and0(BM_sel1, orig), k);
    if(n & 1) {
        b = or0(b, BM_sufix2);
    }

    append_print(a);
    append_print(b);

    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);
    }
}

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() {
    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);
}

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;
}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Wrong answer detected in grader
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Incorrect sorting
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Incorrect sorting
2 Halted 0 ms 0 KB -