[3163] 떨어지는 개미

개미를 실제로 움직이며 시뮬레이션 해봤는데 시간초과가 떴다.

그리고 개미가 마주보면 무조건 뒤 돌게 되는데 문제에 한점에서 겹쳤을 때 뒤 돈다고만 적혀있어서 헷갈렸다.

규칙이 있는데 말로 설명하기가 좀 어렵다.

개미가 한점에서 마주쳤을 때 개미는 서로 처음에 주어진 막대로 떨어지기까지 거리를 맞 교환하게 된다.

따라서 처음에 주어진 거리에서 

아이디가 양수면 오른쪽끝과 현재 포지션사이의 거리

아이디가 음수면 왼쪽끝과 현재 포지션사이의 거리

를 정렬하면 개미가 떨어지기까지 거리를 알 수 있다.

또한 막대 맨 왼쪽 또는 오른쪽에 있는 개미가 우선적으로 떨어지게 된다. 

정렬된 개미 배열에서 거리가 가장 적은 개미 부터 검사해서

개미의 아이디가 양수면 맨 오른쪽 개미가 떨어지고

개미의 아이디가 음수면 맨 왼쪽 개미가 떨어진다.

동시에 개미가 떨어질 경우엔 아이디 절댓값이 작은 개미가 조금 먼저 떨어지기때문에

마지막에 아이디 순으로 정렬을 한번 더 해주면 몇번째 순서에 어떤 개미가 떨어지는지 알 수 있다.

---

#include <cstdio>

#include <vector>

#include <deque>

#include <algorithm>

#include <utility>

using namespace std;

int main(){

int T,N,L,K;

int pos,id;

vector<pair<int,int> > ant;

deque<int> antId;

vector<pair<int, int> > res;

scanf("%d",&T);

while(T > 0){

ant.clear();

antId.clear();

scanf("%d %d %d",&N,&L,&K);

ant = vector<pair<int, int> >(N);

res = vector<pair<int, int> >(N);

for(int i = 0;i<N;i++){

scanf("%d %d",&pos,&id);

if(id > 0){

pos = L - pos;

}

ant[i].first = pos;

ant[i].second = id;

antId.push_back(ant[i].second);

}

sort(ant.begin(),ant.end());

for(int i = 0;i<N;i++){

res[i].first = ant[i].first;

if(ant[i].second > 0){

res[i].second = antId.back();

antId.pop_back();

}else{

res[i].second = antId.front();

antId.pop_front();

}

}

sort(res.begin(),res.end());

printf("%d\n",res[K-1].second);

T--;

}

}