14891번: 톱니바퀴

문제링크

C++

#include <iostream>

using namespace std;

typedef unsigned int uint;

uint g[5];

uint K;

uint g_rot[5];

void rotate_to_left(uint loc, uint rot){
    if (loc - 1 > 0){
        if (((g[loc - 1] & 0b00100000) != 0) != ((g[loc] & 0b00000010) != 0)){
            g_rot[loc - 1] = rot * (-1);
            rotate_to_left(loc - 1, rot * (-1));
        }
    }
}

void rotate_to_right(uint loc, uint rot){
    if (loc + 1 <= 4){
        if ( ( (g[loc + 1] & 0b00000010) != 0) != ( (g[loc] & 0b00100000) != 0) ){
            g_rot[loc + 1] = rot * (-1);
            rotate_to_right(loc + 1, rot * (-1));
        }
    }
}

void rotate(){
    for (uint i = 1; i <= 4; i++){
        if (g_rot[i] == 1){
            if ((g[i] & 1) != 0){
                g[i] >>= 1;
                g[i] |= 0b10000000;
            }else{
                g[i] >>= 1;
            }
        }else if (g_rot[i] == -1){
            if ((g[i] & 0b10000000) != 0){
                g[i] <<= 1;
                g[i] |= 0b1;
                g[i] &= 0b11111111;
            }else{
                g[i] <<= 1;
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    char tmp;
    for (uint i = 1; i <= 4; i++){
        for (uint j = 0; j < 8; j++){
            cin >> tmp;
            if (tmp == '1'){
                uint mask = 1;
                mask <<= 7 - j;
                g[i] |= mask;
            }
        }
    }

    cin >> K;

    for (uint i = 0; i < K; i++){
        uint loc, rot;
        cin >> loc >> rot;
        g_rot[loc] = rot;
        rotate_to_left(loc, rot);
        rotate_to_right(loc, rot);
        rotate();
        for(uint i = 1; i <= 4; i++)
            g_rot[i] = 0;
    }

    cout << 1 * ((g[1] & 0b10000000) != 0) + 2 * ((g[2] & 0b10000000) != 0) + 4 * ((g[3] & 0b10000000) != 0) + 8 * ((g[4] & 0b10000000) != 0) << "\n";

}

• 시뮬레이션
• 비트연산을 사용.
• 하드코딩했는데 조금 단순화할 수 있을 것 같기도..
• $O(K)$