# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
988296 | kachim2 | Arranging Shoes (IOI19_shoes) | C++17 | 445 ms | 281804 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "shoes.h"
#include <climits>
#include <queue>
#include <vector>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
long long count_swaps(std::vector<int> s) {
std::vector<int> pos(s.size(), INT_MIN);
auto qm = new std::queue<int>[s.size()+1];
auto qp = new std::queue<int>[s.size()+1];
for (int i = 0; i < s.size(); i++) {
if (s[i] < 0) {
if (qp[-s[i]].empty()) {
qm[-s[i]].push(i);
} else {
auto x = qp[-s[i]].front();
qp[-s[i]].pop();
pos[i] = x;
}
} else {
if (qm[s[i]].empty()) {
qp[s[i]].push(i);
} else {
auto x = qm[s[i]].front();
qm[s[i]].pop();
pos[i] = x;
}
}
}
long count = 0;
tree<int, null_type, std::less<int>, rb_tree_tag,
tree_order_statistics_node_update>
B;
for (int i = 0; i < s.size(); i++) {
B.insert(i * 3 + 1);
}
for (int i = 0; i < s.size(); i++) {
if (pos[i] >= 0) {
if (s[i] > 0) {
count += B.order_of_key(i * 3 + 1) - B.order_of_key(pos[i] * 3 + 1) - 1;
B.erase(i * 3 + 1);
B.insert(pos[i] * 3 + 2);
} else {
count += B.order_of_key(i * 3 + 1) - B.order_of_key(pos[i] * 3 + 1);
B.erase(i * 3 + 1);
B.insert(pos[i] * 3);
}
}
}
delete[] qm;
delete[] qp;
return count;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |