pstopia Notes for Problem Solving Contest

[C] Queue

Codeforces Round #101 (Div. 2)

Problem

a[i] 가 작은 순으로 정렬해둔다. 0 <= i < n 인 i에 대해, a[i] > i 인 i가 존재하면 조건에 맞는 order가 없는 것이다. 아니라면, 조건에 맞는 order를 항상 만들 수 있다. 리스트를 하나 만들고 0번 사람부터 n-1번 사람까지 차례대로 줄에 끼워넣을 것이다. i번째 사람을 볼 때, 그 사람을 리스트의 a[i]번째 위치에 끼워넣으면 된다. 실제 키 값은 그냥 아무렇게나 배정해도 상관없다.
#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;
}
view raw cf101c.cpp hosted with ❤ by GitHub