[C] Queue
Codeforces Round #101 (Div. 2)
a[i] 가 작은 순으로 정렬해둔다.
0 <= i < n 인 i에 대해, a[i] > i 인 i가 존재하면 조건에 맞는 order가 없는 것이다.
아니라면, 조건에 맞는 order를 항상 만들 수 있다.
리스트를 하나 만들고 0번 사람부터 n-1번 사람까지 차례대로 줄에 끼워넣을 것이다.
i번째 사람을 볼 때, 그 사람을 리스트의 a[i]번째 위치에 끼워넣으면 된다.
실제 키 값은 그냥 아무렇게나 배정해도 상관없다.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <cstdio> | |
| #include <string> | |
| #include <vector> | |
| #include <algorithm> | |
| using namespace std; | |
| struct Dat { | |
| string name; | |
| int front, h; | |
| }; | |
| char buf[100]; | |
| int main() { | |
| int n; | |
| scanf("%d", &n); | |
| vector<Dat> dat(n); | |
| for (int i = 0; i < n; ++i) { | |
| scanf("%s %d", buf, &dat[i].front); | |
| dat[i].name.assign(buf); | |
| } | |
| sort(dat.begin(), dat.end(), [](const Dat& a, const Dat& b) { | |
| return a.front < b.front; | |
| }); | |
| int prvh = n + 1; | |
| vector<int> queue; | |
| for (int i = 0; i < n; ++i) { | |
| if (queue.size() < dat[i].front) { | |
| printf("-1\n"); | |
| return 0; | |
| } | |
| dat[i].h = prvh--; | |
| queue.insert(queue.begin() + dat[i].front, i); | |
| } | |
| for (int i = 0; i < n; ++i) { | |
| printf("%s %d\n", dat[queue[i]].name.c_str(), dat[queue[i]].h); | |
| } | |
| return 0; | |
| } |