Submission #1106373

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106373		azberjibiou	Bit Shift Registers (IOI21_registers)	C++17	58 / 100	2 ms	504 KiB

registers

#include "registers.h"
#include <bits/stdc++.h>
using namespace std;
/*
bool secret[100][2000];
void append_move(int t, int y){for(int i=0;i<2000;i++) secret[t][i]=secret[y][i];}
void append_store(int idx, vector <bool> v){ for(int i=0;i<2000;i++) secret[idx][i]=v[i];}
void append_and(int t, int a, int b){for(int i=0;i<2000;i++) secret[t][i]=(secret[a][i]&secret[b][i]);}
void append_or(int t, int a, int b){for(int i=0;i<2000;i++) secret[t][i]=(secret[a][i]|secret[b][i]);}
void append_not(int t, int y){for(int i=0;i<2000;i++) secret[t][i]=(!secret[y][i]);}
void append_left(int t, int y, int k){for(int i=0;i<2000;i++) secret[t][i]=(i<k ? false : secret[y][i-k]);}
void append_right(int t, int y, int k){for(int i=0;i<2000;i++) secret[t][i]=(i+k>=2000 ? false : secret[y][i+k]);}
void append_add(int t, int a, int b){
    vector <bool> res(2000);
    for(int i=0;i<2000;i++){
        int nv=(int)secret[a][i]+(int)secret[b][i]+(int)res[i];
        res[i]=nv%2;
        if(i!=2000) res[i+1]=nv/2;
        secret[t][i]=res[i];
    }
}
void print(int t){
    for(int i=0;i<32;i++) printf("%d", secret[t][i]);
    printf("\n");
}
*/
void solv0(int n, int k ,int q){
    int bit;
    if(n==2) bit=1;
    else bit=7;
    int tot=(1<<bit);
    // set 1 for a[n+1]~a[2^bit-1]
    vector <bool> v0(2000, false);
    for(int i=n*k;i<tot*k;i++) v0[i]=true;
    if(n!=tot){
        append_store(50, v0);
        append_or(0, 0, 50);
    }
    for(int i=0;i<bit;i++){
        vector <bool> v1(2000, false), v2(2000, false);
        for(int j=0;j<tot;j++){
            if(j%(1<<(i+1))==0){
                for(int z=j*k;z<(j+1)*k;z++) v1[z]=true;
            }
            else if(j%(1<<i)==0){
                for(int z=j*k;z<(j+1)*k;z++) v2[z]=true;
            }
        }
        // 1: 2^(i+1)x번째 값, 2: 2^(i+1)x+2^i번째 값
        append_store(51, v1);
        append_store(52, v2);
        append_move(1, 0);
        append_move(2, 0);
        append_and(1, 1, 51);
        append_and(2, 2, 52);
        append_right(2, 2, (1<<i)*k);
        // 3: !2, 4: 1+3의 k+1번째 자리
        //!y = 2^b-1 - y
        // x + !y < 2^b <=> x+2^b-1-y < 2^b <=> x-y-1<0 <=> x<=y
        // k+1번째 자리가 0 <=> x<=y
        append_not(3, 2);
        append_and(3, 3, 51);
        append_add(4, 1, 3);
        vector <bool> v3(2000, false);
        for(int j=0;j<tot;j++){
            if(j%(1<<(i+1))==0) v3[(j+1)*k]=true;
        }
        append_store(53, v3);
        append_and(4, 4, 53);
        append_right(4, 4, k);
        //5: 0 -> 1111, 1 -> 0000, 6: !5
        append_add(5, 4, 51);
        append_and(5, 5, 51);
        append_not(6, 5);
        append_and(6, 6, 51);
        //0: 5&1+6&2
        append_and(7, 5, 1);
        append_and(8, 6, 2);
        append_add(0, 7, 8);
    }
}
void solv1(int n, int k, int q){
 
    //set 1 for a[n+1]~a[127]
    vector <bool> v0(2000, false);
    for(int i=n*k;i<16*k;i++) v0[i]=true;
    append_store(50, v0);
    append_or(0, 0, 50);
    //printf("0: "); print(0);
    for(int i=0;i<4;i++){
        //v1: 1010..., 11001100...
        vector <bool> v1(2000, false);
        for(int j=0;j<16;j++){
            if(j%(1<<(i+1))<(1<<i)) for(int z=j*k;z<(j+1)*k;z++) v1[z]=true;
        }
        append_store(51, v1);
        //printf("51: "); print(51);
        // v2: 2^i-1번째만 가져옴
        vector <bool> v2(2000, false);
        for(int j=0;j<16;j++){
            if(j%(1<<(i+1))==(1<<i)-1) for(int z=j*k;z<(j+1)*k;z++) v2[z]=true;
        }
        append_store(52, v2);
        //printf("52: "); print(52);
        //v3: 2^i-1번째의 받아올림 자리만 가져옴
        vector <bool> v3(2000, false);
        for(int j=0;j<16;j++){
            if(j%(1<<(i+1))==(1<<i)-1) v3[(j+1)*k]=true;
        }
        append_store(53, v3);
        //printf("53: "); print(53);
        //v4: 0~2^i-1번째 자리만 가져옴
        vector <bool> v4(2000, false);
        for(int j=0;j<16;j++){
            if(j%(1<<(i+1))<=(1<<i)-1) for(int z=j*k;z<(j+1)*k;z++) v4[z]=true;
        }
        append_store(54, v4);
        //printf("54: "); print(54);
        
        // 1: 2^(i+1)개 기준으로 앞에 절반, 2: 뒤에 절반
        append_and(1, 0, 51);
        append_right(2, 0, k*(1<<i));
        append_and(2, 2, 51);
        for(int j=0;j<(1<<(i+1));j++){
            //printf("1: "); print(1);
            //printf("2: "); print(2);
            //5: !2
            append_not(5, 2);
            append_and(5, 5, 52);
            //6: 1+!2
            append_add(6, 1, 5);
            //printf("6: "); print(6);
            //7: 3+!4의 받아올림자리
            append_and(7, 6, 53);
            append_right(7, 7, k*(1<<i));
            //printf("7: "); print(7);
            //8: 0 -> 1111, 1 -> 0000, 9: !8
            append_add(8, 7, 54);
            append_and(8, 8, 54);
            append_not(9, 8);
            append_and(9, 9, 54);
            //printf("8: "); print(8);
            //printf("9: "); print(9);
            //x+!y<2^k => x<y+1 => max(x, y)=y
            //8=0000 => x+!y>=2^k => x>=y => 3
            //12: 9&1+8&2
            append_and(10, 9, 1);
            append_and(11, 8, 2);
            append_add(12, 10, 11);
            //printf("12: "); print(12);
            //13: 12를 자기 위치로 옮기기
            if(j<(1<<i)) append_left(13, 12, ((1<<i)-j)*k);
            else append_right(13, 12, (j-(1<<i))*k);
            //99: 정렬 후
            //printf("13: "); print(13);
            append_or(99, 13, 99);
            //14: 1을 shift, 15: 2를 shift
            append_left(14, 1, k);
            append_left(15, 2, k);
            //printf("14: "); print(14);
            //printf("15: "); print(15);
            //8=0000 => x>=y => 1을 shift
            //1=9&14+8&1
            append_and(16, 9, 14);
            append_and(17, 8, 1);
            append_add(1, 16, 17);
            append_and(1, 1, 54);
            //2=8&15+9&2
            append_and(18, 8, 15);
            append_and(19, 9, 2);
            //printf("18: "); print(18);
            //printf("19: "); print(19);
            append_add(2, 18, 19);
            append_and(2, 2, 54);
            //printf("2: "); print(2);
            //printf("99: "); print(99);
        }
        append_move(0, 99);
        vector <bool> v5(2000, false);
        append_store(99, v5);
    }
}
void construct_instructions(int s, int n, int k, int q) {
    if(s==0){
        solv0(n, k, q);
    }
    else{
        solv1(n, k, q);
    }
}
/*
int main(){
    secret[0][0]=secret[0][1]=secret[0][3]=secret[0][4]=true;
    //secret[0]={true, true, true, false, true, false, false, true};
    construct_instructions(1, 4, 2, 1557);
    for(int i=0;i<8;i++) printf("%d", secret[0][i]);
}
*/

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