QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#768234 | #2337. Azulejos | wxhtzdy | AC ✓ | 652ms | 42472kb | C++20 | 2.4kb | 2024-11-21 03:57:13 | 2024-11-21 03:57:13 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<int> pa(n);
for (int i = 0; i < n; i++) {
cin >> pa[i];
}
vector<int> ha(n);
for (int i = 0; i < n; i++) {
cin >> ha[i];
}
vector<int> pb(n);
for (int i = 0; i < n; i++) {
cin >> pb[i];
}
vector<int> hb(n);
for (int i = 0; i < n; i++) {
cin >> hb[i];
}
vector<int> order_a(n);
iota(order_a.begin(), order_a.end(), 0);
sort(order_a.begin(), order_a.end(), [&](int i, int j) {
return pa[i] < pa[j];
});
vector<int> order_b(n);
iota(order_b.begin(), order_b.end(), 0);
sort(order_b.begin(), order_b.end(), [&](int i, int j) {
return pb[i] < pb[j];
});
vector<int> res_a;
vector<int> res_b;
set<pair<int, int>> st_a;
set<pair<int, int>> st_b;
int ptr_a = 0;
int ptr_b = 0;
while ((!st_a.empty() || ptr_a < n) && (!st_b.empty() || ptr_b < n)) {
if (st_a.empty()) {
int id = ptr_a;
while (ptr_a < n && pa[order_a[ptr_a]] == pa[order_a[id]]) {
st_a.emplace(ha[order_a[ptr_a]], order_a[ptr_a]);
ptr_a += 1;
}
}
if (st_b.empty()) {
int id = ptr_b;
while (ptr_b < n && pb[order_b[ptr_b]] == pb[order_b[id]]) {
st_b.emplace(hb[order_b[ptr_b]], order_b[ptr_b]);
ptr_b += 1;
}
}
if (int(st_a.size()) < int(st_b.size())) {
for (auto& p : st_a) {
int h = p.first;
int id = p.second;
auto it = st_b.lower_bound({h, -1});
if (it == st_b.begin()) {
break;
}
it = prev(it);
res_a.push_back(id);
res_b.push_back(it->second);
st_b.erase(it);
}
st_a.clear();
} else {
for (auto& p : st_b) {
int h = p.first;
int id = p.second;
auto it = st_a.lower_bound({h + 1, -1});
if (it == st_a.end()) {
break;
}
res_a.push_back(it->second);
res_b.push_back(id);
st_a.erase(it);
}
st_b.clear();
}
}
if (int(res_a.size()) != n || int(res_b.size()) != n) {
cout << "impossible" << '\n';
} else {
for (int i = 0; i < n; i++) {
cout << res_a[i] + 1 << " ";
}
cout << '\n';
for (int i = 0; i < n; i++) {
cout << res_b[i] + 1 << " ";
}
cout << '\n';
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3632kb
Test #2:
score: 0
Accepted
time: 0ms
memory: 3860kb
Test #3:
score: 0
Accepted
time: 0ms
memory: 3504kb
Test #4:
score: 0
Accepted
time: 0ms
memory: 3872kb
Test #5:
score: 0
Accepted
time: 0ms
memory: 3628kb
Test #6:
score: 0
Accepted
time: 0ms
memory: 3624kb
Test #7:
score: 0
Accepted
time: 0ms
memory: 3556kb
Test #8:
score: 0
Accepted
time: 0ms
memory: 3632kb
Test #9:
score: 0
Accepted
time: 0ms
memory: 3560kb
Test #10:
score: 0
Accepted
time: 0ms
memory: 3628kb
Test #11:
score: 0
Accepted
time: 0ms
memory: 3564kb
Test #12:
score: 0
Accepted
time: 208ms
memory: 38192kb
Test #13:
score: 0
Accepted
time: 0ms
memory: 3564kb
Test #14:
score: 0
Accepted
time: 1ms
memory: 3588kb
Test #15:
score: 0
Accepted
time: 5ms
memory: 4316kb
Test #16:
score: 0
Accepted
time: 0ms
memory: 3624kb
Test #17:
score: 0
Accepted
time: 0ms
memory: 3564kb
Test #18:
score: 0
Accepted
time: 0ms
memory: 3824kb
Test #19:
score: 0
Accepted
time: 0ms
memory: 3564kb
Test #20:
score: 0
Accepted
time: 0ms
memory: 3872kb
Test #21:
score: 0
Accepted
time: 1ms
memory: 3680kb
Test #22:
score: 0
Accepted
time: 58ms
memory: 6644kb
Test #23:
score: 0
Accepted
time: 59ms
memory: 10160kb
Test #24:
score: 0
Accepted
time: 84ms
memory: 10080kb
Test #25:
score: 0
Accepted
time: 35ms
memory: 6568kb
Test #26:
score: 0
Accepted
time: 186ms
memory: 38324kb
Test #27:
score: 0
Accepted
time: 36ms
memory: 10164kb
Test #28:
score: 0
Accepted
time: 68ms
memory: 11240kb
Test #29:
score: 0
Accepted
time: 41ms
memory: 10344kb
Test #30:
score: 0
Accepted
time: 36ms
memory: 10200kb
Test #31:
score: 0
Accepted
time: 652ms
memory: 42472kb
Test #32:
score: 0
Accepted
time: 74ms
memory: 11200kb
Test #33:
score: 0
Accepted
time: 514ms
memory: 42440kb