[백준] 20364 부동산 다툼, python, C++

https://www.acmicpc.net/problem/20364

20364번: 부동산 다툼

이진 트리로 풀어야할 것 같지만 shift 연산만 사용하면된다.

 

# import sys; input = sys.stdin.readline
def check_owned(x, owned):
    land = 0
    while x > 0:
        if owned[x]:
            land = x
        x >>= 1
    return land

N, Q = map(int, input().split())
owned = [False for _ in range(N + 1)]
for i in range(Q):
    x = int(input())

    owned_land = check_owned(x, owned)
    if not owned_land:
        owned[x] = True
    print(owned_land)

#include<iostream>
using namespace std;

bool owned[(1 << 20) + 1] = { 0, };
int check_owned(int x) {
    int land = 0;
    while (x) 
    {
        if (owned[x])
            land = x;
        x >>= 1;
    }
    return land;
}

int main() {
    int N, Q, i, num, land;
    cin >> N >> Q;
    
    for (i = 0; i < Q; i++)
    {
        cin >> num;
        land = check_owned(num);
        if (!land)
            owned[num] = true;
        cout << land << '\n';
        
    } 

    return 0;
}