QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#531742 | #2337. Azulejos | Swarthmore# | WA | 0ms | 3804kb | C++14 | 2.9kb | 2024-08-24 22:00:35 | 2024-08-24 22:00:36 |
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++;
}
// 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();
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;
}
Details
Test #1:
score: 100
Accepted
time: 0ms
memory: 3596kb
Test #2:
score: 0
Accepted
time: 0ms
memory: 3740kb
Test #3:
score: 0
Accepted
time: 0ms
memory: 3776kb
Test #4:
score: 0
Accepted
time: 0ms
memory: 3804kb
Test #5:
score: 0
Accepted
time: 0ms
memory: 3584kb
Test #6:
score: 0
Accepted
time: 0ms
memory: 3768kb
Test #7:
score: 0
Accepted
time: 0ms
memory: 3584kb
Test #8:
score: -100
Wrong Answer
time: 0ms
memory: 3596kb