QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#531728 | #2337. Azulejos | Swarthmore# | WA | 1ms | 3840kb | C++14 | 2.5kb | 2024-08-24 21:56:17 | 2024-08-24 21:56:19 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
struct rec {
int p, h;
int id;
bool operator<(const rec & r) const {
if (p != r.p) return p < r.p;
return h < r.h;
}
};
int main() {
int n;
cin >> n;
vector<rec> a(n), b(n);
vector<int> pa(n), pb(n);
for (int i = 0; i < n; i++) {
cin >> a[i].p;
pa[i] = a[i].p;
a[i].id = i;
}
for (int i = 0; i < n; i++) {
cin >> a[i].h;
}
for (int i = 0; i < n; i++) {
cin >> b[i].p;
pb[i] = b[i].p;
b[i].id = i;
}
for (int i = 0; i < n; i++) {
cin >> b[i].h;
}
sort(a.begin(), a.end());
sort(b.begin(), b.end());
vector<int> ansa(n), ansb(n);
int i = 0, j = 0;
set<pair<int, int>> ah, bh;
unordered_map<int, int> bl;
int ct = 0;
for (int i = 0; i < n; i++) {
if (bl.find(b[i].p) == bl.end()) {
bl[b[i].p] = i;
}
}
while (ct < n) {
// Add all with price equal to current a[i]
int cura = a[i].p;
while (i < n && a[i].p == cura) {
ah.insert({a[i].h, a[i].id});
i++;
}
int bp = b[i-1].p;
while (j < n && b[j].p < bp) {
bh.insert({b[j].h, b[j].id});
j++;
}
// Add those equal to b[j].p later, we must match them
for (auto [h, id] : bh) {
auto it = ah.upper_bound({h, n});
if (it == ah.end()) {
cout << "impossible\n";
return 0;
}
ansa[bl[pb[id]]] = it->second;
ansb[bl[pb[id]]] = id;
bl[pb[id]]++;
ct++;
ah.erase(it);
}
bh.clear();
while (j < n && b[j].p == bp) {
bh.insert({b[j].h, b[j].id});
j++;
}
for (auto [h, id] : ah) {
auto it = bh.lower_bound({h, -1});
if (it == bh.begin()) {
cout << "impossible\n";
return 0;
}
it--;
ansa[bl[bp]] = id;
ansb[bl[bp]] = it->second;
bl[bp]++;
ct++;
bh.erase(it);
}
ah.clear();
}
for (int i = 0; i < n; i++) {
cout << ansa[i] + 1 << " ";
}
cout << endl;
for (int i = 0; i < n; i++) {
cout << ansb[i] + 1 << " ";
}
cout << endl;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3644kb
Test #2:
score: 0
Accepted
time: 1ms
memory: 3840kb
Test #3:
score: 0
Accepted
time: 1ms
memory: 3544kb
Test #4:
score: 0
Accepted
time: 1ms
memory: 3556kb
Test #5:
score: 0
Accepted
time: 1ms
memory: 3584kb
Test #6:
score: 0
Accepted
time: 1ms
memory: 3780kb
Test #7:
score: 0
Accepted
time: 1ms
memory: 3780kb
Test #8:
score: -100
Wrong Answer
time: 0ms
memory: 3500kb