oj.uz

Submission #631040

# Submission time Handle Problem Language Result Execution time Memory
631040 2022-08-17T15:18:26 Z qwerasdfzxcl Bit Shift Registers (IOI21_registers) C++17
100 / 100
 2 ms 652 KB 
#include "registers.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

void init0(int n, int k){
    vector<bool> V(2000, 0);

    for (int i=k*n;i<2000;i++) V[i] = 1;
    append_store(71, V);

    for (int z=1;z<=(n==2?1:7);z++){
        fill(V.begin(), V.end(), 0);
        for (int i=0;i<128;i++) if (i%(1<<z)==0){
            for (int j=i*k;j<(i+1)*k;j++) V[j] = 1;
        }

        append_store(90+z, V);
        append_not(80+z, 90+z);
    }
}

void copy_bit(int t, int k){
    ++k;
    int len = 1;
    while(len<k){
        if (len*2 <= k) append_right(61, t, len);
        else append_right(61, t, k-len);
        append_or(t, t, 61);

        len *= 2;
    }
}

void solve0(int n, int k){
    init0(n, k);

    append_or(0, 0, 71);

    for (int z=0;z<(n==2?1:7);z++){
        append_right(1, 0, k*(1<<z));
        if (z==0){append_and(0, 0, 91); append_and(1, 1, 91);}
        append_xor(2, 0, 1);
        append_xor(1, 1, 90+z+1);

        append_add(1, 0, 1);
        append_and(1, 1, 80+z+1);

        copy_bit(1, k);

        append_and(1, 1, 2);
        append_xor(0, 0, 1);
        append_and(0, 0, 90+z+1);
    }

}

int cncnt = 0;
void copy_number(int t, int cnt, int k){
    ++cnt;
    int len = 1;
    while(len<cnt){
        cncnt += 2;

        if (len*2<=cnt) append_right(61, t, k*2*len);
        else append_right(61, t, k*2*(cnt-len));
        append_or(t, t, 61);
        len *= 2;
    }
}

void split(int n, int k){
    vector<bool> V(2000, 0);
    for (int i=0;i<n;i++) if (i&1){
        for (int j=i*k;j<(i+1)*k;j++) V[j] = 1;
    }

    append_store(99, V);
    append_and(98, 0, 99);
    append_xor(97, 0, 98);
    append_left(98, 98, k*n-(n%2?0:k));
    append_or(0, 97, 98);
}

void recover(int n, int k){
    for (int z=0;z<7;z++){
        vector<bool> V(2000, 0);
        for (int i=0;i<n*2;i++) if (i&(1<<(z+1))){
            for (int j=i*k;j<(i+1)*k;j++) V[j] = 1;
        }

        append_store(99, V);
        append_and(98, 0, 99);
        append_xor(97, 0, 98);
        append_right(98, 98, k*(1<<z));
        append_or(0, 97, 98);
    }
}

void init1(int n, int k){
    vector<bool> V(2000, 0);
    for (int i=0;i<k;i++) V[i] = 1;
    append_store(91, V);

    fill(V.begin(), V.end(), 0);
    for (int i=0;i<2000;i++) if (i%(k*2)==k) V[i] = 1;
    append_store(92, V);

    fill(V.begin(), V.end(), 0);
    for (int i=0;i<2000;i++) if (i%(k*2)<k) V[i] = 1;
    append_store(93, V);
}

void solve1(int n, int k){
    split(n, k);
    init1(n, k);

    for (int i=1;i<n;i++){
        append_left(91, 91, k*2);
        append_and(2, 0, 91);
        append_xor(1, 0, 2);

        append_xor(2, 2, 91);
        copy_number(2, i, k);

        append_add(3, 1, 2);
        append_and(3, 3, 92);
        copy_bit(3, k);

        append_and(13, 1, 3);
        append_left(13, 13, k*2);

        append_not(4, 3);
        append_and(11, 1, 4);

        append_not(2, 2);
        append_xor(4, 4, 91);
        append_left(5, 3, k*2);
        append_or(5, 4, 5);
        append_not(5, 5);
        append_and(12, 2, 5);

        append_or(0, 11, 12);
        append_or(0, 0, 13);

        append_and(0, 0, 93);
    }

    recover(n, k);

    //printf("%d\n", cncnt);
    //exit(0);
}

void construct_instructions(int s, int n, int k, int q) {
	if (s==0) solve0(n, k);
	if (s==1) solve1(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
11.0 / 11.0

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

Subtask #3
12.0 / 12.0

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

Subtask #5
13.0 / 13.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

Subtask #6
29.0 / 29.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 2 ms 628 KB Output is correct
4 Correct 2 ms 652 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct