[백준] 23326번 홍익 투어리스트 (C++)

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

 

 

이 문제는 N개의 구역을 입력하고 명소의 위치, 이후 3개의 쿼리 중 하나씩 입력이 들어올때 그에 맞게 결과를 출력하는 문제이다.

 

1번 쿼리는 다음 입력으로 구역이 입력되며 다음 입력이 만약 명소로 지정되어 있는 경우 지정이 풀리며

지정이 안되어 있는 경우 지정된다.

 

2번 쿼리는 시계방향으로 x만큼 이동한다.

 

3번 쿼리는 현재 위치에서 시계방향으로 이동할때 가장 가까운 명소에 도착할때 몇칸 이동해야 하는지 출력해야한다.

 

이때 구역(N)의 개수가 최대 50만이고 쿼리의 개수가 최대 10만이다.

 

3번쿼리는 가장 가까운 명소를 탐색해야하기 때문에 일일히 다 확인하기엔 시간초과가 난다.

 

따라서 이분탐색 여기서는 lower_bound 함수를 사용하여 log N으로 구현하였다.

 

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

int dx[] = {0 ,0, -1, 0, 1, 1, -1, -1, 1};
int dy[] = {0, -1, 0, 1, 0, -1, 1, -1, 1};
int N, Q;
int arr[500001];
set<int> st;

void solve() {
    int idx = 1;

    for(int i = 0; i < Q; i++) {
        int a, b;
        cin >> a;

        if(a == 1) {
            cin >> b;
            if(st.find(b) != st.end()) {      // 존재하는 경우
                st.erase(b);
            }
            else st.insert(b);
        }
        else if(a == 2) {
            cin >> b;
            idx = (idx + b) % N;
            if(idx == 0) idx = N;
        }
        else {
            if(st.empty()) {
                cout << -1 << endl;
                continue;
            }
            
            auto left = st.lower_bound(idx);

            if(left == st.end()) {
                auto it = st.begin();
                cout << *it + (N - idx) << endl;
            }
            else {
                cout << *left - idx << endl;
            }
        }
    }
}

void input() {
    cin >> N >> Q;

    for(int i = 1; i <= N; i++) {
        int a;
        cin >> a;
        if(a == 1) st.insert(i);
    }

    solve();
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
}