Submission #1106357

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

registers

#include "registers.h"
 #include <bits/stdc++.h>
using namespace std;
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);
    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);
        // 1: 2^(i+1)개 기준으로 앞에 절반, 2: 뒤에 절반
        append_and(1, 0, 51);
        append_right(2, 0, k*(1<<i));
        append_and(2, 2, 51);
 
        // v2: 2^i-1번째만 가져옴
        vector <bool> v2(2000, false);
        for(int j=0;j<n;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);
        //v3: 2^i-1번째의 받아올림 자리만 가져옴
        vector <bool> v3(2000, false);
        for(int j=0;j<n;j++){
            if(j%(1<<(i+1))==(1<<i)-1) v2[(j+1)*k]=true;
        }
        append_store(53, v3);
        //v4: 0~2^i-1번째 자리만 가져옴
        vector <bool> v4(2000, false);
        for(int j=0;j<n;j++){
            if(j%(1<<(i+1))<=(1<<i)-1) for(int z=j*k;z<(j+1)*k;z++) v2[z]=true;
        }
        append_store(54, v4);
        for(int j=0;j<(1<<(i+1));j++){
            //3, 4: 1, 2의 중요 원소만 가져옴
            append_and(3, 1, 52);
            append_and(4, 2, 52);
            //5: !4
            append_not(5, 4);
            //6: 3+!4
            append_add(6, 3, 5);
            //7: 3+!4의 받아올림자리
            append_and(7, 6, 53);
            append_right(7, 7, k*(1<<i));
            //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);
            //x+!y<2^k => x<y+1 => max(x, y)=y
            //8=0000 => x+!y>=2^k => x>=y => 3
            //12: 9&3+8&4
            append_and(10, 9, 3);
            append_and(11, 8, 4);
            append_add(12, 10, 11);
            //13: 12를 자기 위치로 옮기기
            append_right(13, 12, j*k);
            //99: 정렬 후
            append_or(99, 13, 12);
            //14: 1을 shift, 15: 2를 shift
            append_left(14, 1, k);
            append_left(15, 2, k);
            //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);
            //2=8&15+9&2
            append_and(18, 8, 15);
            append_and(19, 9, 2);
            append_add(2, 18, 19);
        }
        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);
    }
}

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