핵심 아이디어

<aside> 💡

구현 문제

• 입실, 퇴실 시간을 처리해야하는 순서로 정렬 할 수 있도록 하는 우선순위 큐
• 각 자리의 사용 여부를 체크하는 배열
• 각 사람이 현재 어떤 자리를 사용하는 지 저장하는 배열
• 입실의 경우 현재 앉을 수 있는 자리를 이분탐색으로 서칭 </aside>

코드

#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
using namespace std;
typedef long long int ll;

int N, T, P;

bool v[104];
int pos[501];

struct compare
{
    bool operator()(tuple<int, int, int, int> &fs, tuple<int, int, int, int> &sc)
    {
        auto[ft, fo, fe, fi] = fs;
        auto[st, so, se, si] = sc;
        
        if(ft == st && fo == so) return fe>se;
        if(ft == st) return fo>so;
        return ft>st;
    }
};

priority_queue<tuple<int,int,int,int>, vector<tuple<int,int,int,int>>, compare> pq;

pair<int, int> qry[501];

signed main()
{
    FASTIO;
    cin >> N >> T >> P;
    for(int i = 0; i<T; i++){
        int s, e;
        cin >> s >> e;
        if(s!=e){
            pq.push({s/100*60+s%100, 1, e, i});
            pq.push({e/100*60+e%100, 0, 1260,i});
        }
    }

    int ans = 0;
    for(int cur = 9*60; cur<21*60; cur++){
        while(!pq.empty()){
            auto[t, o, et, idx] = pq.top();
            if(t != cur){
                break;
            }
            pq.pop();
            
            //나감
            if(!o){
                v[pos[idx]] = false;
                pos[idx] = 0;
            }
            //들어옴
            else{
                //가장 멀리 앉을 수 있는 거리 lo
                int lo = 0, hi = N;
                while(lo+1<hi){
                    int mid = lo+hi>>1;
                    bool flag = false;
                    for(int i = 1; i<=N; i++){
                        if(v[i]) continue;
                        bool lflag = true;
                        bool rflag = true;
                        for(int j = i; j>=max(1,i-mid); j--){
                            if(v[j]){
                                lflag = false;
                                break;
                            }
                        }
                        for(int j = i; j<=min(N, i+mid); j++){
                            if(v[j]){
                                rflag = false;
                                break;
                            }
                        }

                        if(lflag && rflag){
                            flag = true;
                            break;
                        }
                    }

                    if(flag) lo = mid;
                    else hi = mid;
                }

                //앉음
                for(int i = 1; i<=N; i++){
                    if(v[i]) continue;
                    bool lflag = true;
                    bool rflag = true;
                    for(int j = i; j>=max(1,i-lo); j--){
                        if(v[j]){
                            lflag = false;
                            break;
                        }
                    }
                    for(int j = i; j<=min(N, i+lo); j++){
                        if(v[j]){
                            rflag = false;
                            break;
                        }
                    }

                    if(lflag && rflag){
                        v[i] = true;
                        pos[idx] = i;
                        break;
                    }
                }

            }
        }

        if(!v[P]){
            ans++;
        }
    }
    cout << ans <<"\\n";
    
    return 0;
}