oj.uz

Submission #1106354

# Submission time Handle Problem Language Result Execution time Memory
1106354 2024-10-30T04:37:50 Z azberjibiou Bit Shift Registers (IOI21_registers) C++17
58 / 100
 1 ms 760 KB 
#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<128*k;i++) v0[i]=true;
    append_store(50, v0);
    append_or(0, 0, 50);
    for(int i=0;i<7;i++){
        //v1: 1010..., 11001100...
        vector <bool> v1(2000, false);
        for(int j=0;j<128;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.0 / 10.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 760 KB Wrong answer detected in grader
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 760 KB Wrong answer detected in grader
2 Halted 0 ms 0 KB -