[3163] 떨어지는 개미

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

3163번: 떨어지는 개미

<문제>

핵심 아이디어는 개미가 다른 개미를 통과한다고 생각하는 것이다.

개미의 충돌을 구현할 필요가 없다면, 개미가 떨어지기까지 남은 턴은 간단한 식으로 계산이 가능하다.

이후에 동시에 떨어지는 부분에 대한 처리만 구현하면 되는데...

 

실제로 시뮬레이션을 한다고 생각했을때, 개미간의 순서는 항상 바뀌지 않는다
(물론, 양끝에서 개미가 떨어져서 삭제될 수 있다.)

위 관찰을 해내는건 그리 어렵지 않지만, 그래서인지 관찰과 풀이간의 거리가 좀 멀게 느껴진다.

관찰을 조금 더 쉽게 풀이로 이끌어 낼 방법을 조금 더 고민해볼 필요가 있겠다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int t, n, l, k;
typedef struct {
    int pos, id;
} state;
using pi = pair<int, int>;
vector<state> v;
vector<pi> downTime;
vector<pi> ans;
deque<int> dq;
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while (t--) {
        int i;
        v.clear();
        downTime.clear();
        ans.clear();
        dq.clear();
        cin >> n >> l >> k;
        v.resize(n);
        downTime.resize(n);
        ans.resize(n);
        for (i = 0; i < n; i++) cin >> v[i].pos >> v[i].id;
        for (i = 0; i < n; i++) {
            if (v[i].id > 0)
                downTime[i] = {l - v[i].pos + 1, v[i].id};
            else
                downTime[i] = {v[i].pos + 1, v[i].id};
        }
        sort(downTime.begin(), downTime.end());
        for (i = 0; i < n; i++) dq.push_back(v[i].id);
        for (i = 0; i < n; i++) {
            if (downTime[i].second > 0) {
                ans[i] = {downTime[i].first, dq.back()};
                dq.pop_back();
            } else {
                ans[i] = {downTime[i].first, dq.front()};
                dq.pop_front();
            }
        }
        sort(ans.begin(), ans.end());
        cout << ans[k - 1].second << '\n';
    }
    return 0;
}