Submission #1107052

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107052		azberjibiou	Bit Shift Registers (IOI21_registers)	C++17	100 / 100	4 ms	1212 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_xor(int t, int a, int b){for(int i=0;i<2000;i++) secret[t][i]=secret[a][i]^secret[b][i];}
void append_left(int t, int y, int k){
    vector <bool> tmp(2000, false);
    for(int i=0;i<2000;i++) tmp[i]=(i<k ? false : secret[y][i-k]);
    for(int i=0;i<2000;i++) secret[t][i]=tmp[i];
}
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> tmp(2000, false);
    for(int i=0;i<2000;i++){
        int nv=(int)secret[a][i]+(int)secret[b][i]+(int)tmp[i];
        tmp[i]=nv%2;
        if(i!=2000) tmp[i+1]=nv/2;
    }
    for(int i=0;i<2000;i++) secret[t][i]=tmp[i];
}
void print(int t){
    printf("%2d: ", t);
    for(int i=0;i<32;i++) printf("%d", secret[t][i]);
    printf("\n");
}
*/
void print(int t){}
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){
    vector <bool> v0(2000, false);
    for(int i=0;i<2*n;i++) if(i%2==1) for(int j=i*k;j<(i+1)*k;j++) v0[j]=true;
    append_store(50, v0);
    //make space between elements
    append_and(1, 0, 50);
    append_xor(0, 0, 1);
    print(0);
    print(1);
    int del=(n%2==0 ? n-1 : n);
    append_left(1, 1, del*k);
    print(1);
    append_or(0, 0, 1);
 
    //99: ans
    append_left(99, 0, 2000-k);
    append_right(99, 99, 2000-k);
    print(0);
    //53: 0~i번째 원소 자리의 k번째 자리만 true, 밖으로 빼내도 됨
    vector <bool> v3(2000, false);
    for(int j=0;j<n;j++) v3[(2*j+1)*k]=true;
    append_store(53, v3);
    for(int i=1;i<n;i++){
        print(99);
        // 51: i번째 원소 자리만 true
        vector <bool> v1(2000, false);
        for(int j=2*i*k;j<(2*i+1)*k;j++) v1[j]=true;
        append_store(51, v1);
        //52: 0~i번째 원소 자리만 true
        vector <bool> v2(2000, false);
        for(int j=0;j<=i;j++) for(int z=2*j*k;z<(2*j+1)*k;z++) v2[z]=true;
        append_store(52, v2);
        //2: ai를 0~i까지 복사
        append_and(2, 0, 51);
        int pos=i, b=0;
        while(pos>0){
            append_right(3, 2, 2*(1<<b)*k);
            append_or(2, 2, 3);
            pos-=(1<<b);
            b++;
        }
        //4: 0~i-1까지 정렬된 aj + ai
        append_and(4, 0, 51);
        append_or(4, 4, 99);
        //5: !4
        append_not(5, 4);
        append_and(5, 52, 5);
        //6: !4+2
        append_add(6, 5, 2);
        print(6);
        //7: 덧셈의 결과 자리를 일의 자리로 옮기기
        //ai+!aj>=2^k => aj<ai => 7=1 => 8=0
        append_and(7, 6, 53);
        append_right(7, 7, k);
        print(7);
        //8: (!7)로 0~k-1번째 자리 채우기
        append_add(8, 7, 52);
        //9: 8을 오른쪽으로 1칸 시프트
        append_left(9, 8, 2*k);
        //10: 4를 오른쪽으로 1칸 시프트
        append_left(10, 4, 2*k);
 
        /* 중간 정리
        2: ai 복사본
        4. 0~i-1까지 정렬된 aj + ai
        10. 1칸 시프트된 4
        (8, 9)=
        (0, 0) => aj
        (1, 0) => ai
        (1, 1) => a_{j-1}
        want: !1&aj+1&(!2&ai+2&a{j-1})
        */
 
        print(2);
        print(4);
        print(10);
        print(8);
        print(9);
 
        //11: !8
        append_not(11, 8);
        append_and(11, 52, 11);
        //12: !9
        append_not(12, 9);
        append_and(12, 52, 12);
        //99: 11&4+8&(12&2+9&10)
        append_and(13, 11, 4);
        append_and(14, 12, 2);
        append_and(15, 9, 10);
        append_add(16, 14, 15);
        append_and(17, 8, 16);
        append_add(99, 13, 17);
        print(13);
        print(17);
 
    }
    print(99);
    //remove space between elements
    for(int i=1;i<n;i++){
        append_right(98, 99, i*k);
        append_left(98, 98, (i-1)*k);
        append_left(97, 99, 2000-i*k);
        append_right(97, 97, 2000-i*k);
        append_or(99, 98, 97);
    }
    append_move(0, 99);
}
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][2]=secret[0][3]=true;
    //secret[0]={true, true, true, false, false, true, false, false};
    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: 13 / 13
• Subtask 6: 29 / 29