Submission #1060065

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060065		vjudge1	Bit Shift Registers (IOI21_registers)	C++17	10 / 100	1 ms	348 KiB

registers

#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_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);
    free(minc);
    return re;
}


int min0(int b, int c) {
    int d = dif(b, c); /// b - c, 0 / 1,  ... 
    int d0 = d;
    d = and0(d, BM_sel1);
    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 ...
    return dif(b, e);
}


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

• Subtask 1: 10 / 10
• Subtask 2: 0 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 25
• Subtask 5: 0 / 13
• Subtask 6: 0 / 29