QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#213940 | #2337. Azulejos | ucup-team2172# | AC ✓ | 444ms | 44484kb | C++14 | 2.8kb | 2023-10-14 16:42:13 | 2023-10-14 16:42:13 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 500005;
int n, p[2][N], h[2][N], ans1[N], ans2[N];
struct st {
int i, p, h;
}t1[N], t2[N];
bool cmp(st a, st b) {
return (a.p != b.p) ? a.p < b.p : a.h < b.h;
}
set<pair<int, int> > S1, S2;
int main() {
scanf("%d", &n);
for (int i=1;i<=n;++i) scanf("%d", &t1[i].p);
for (int i=1;i<=n;++i) scanf("%d", &t1[i].h);
for (int i=1;i<=n;++i) scanf("%d", &t2[i].p);
for (int i=1;i<=n;++i) scanf("%d", &t2[i].h);
for (int i=1;i<=n;++i) {
t1[i].i=i;
t2[i].i=i;
}
sort(t1+1,t1+n+1,cmp);
sort(t2+1,t2+n+1,cmp);
int p1 = 1, p2 = 1;
S1.clear();
S2.clear();
while (p1<=n && t1[p1].p == t1[1].p) {
S1.insert(make_pair(t1[p1].h, t1[p1].i));
p1++;
}
while (p2<=n && t2[p2].p == t2[1].p) {
S2.insert(make_pair(t2[p2].h, t2[p2].i));
p2++;
}
int k = 0;
while (true) {
int n1 = S1.size(), n2 = S2.size();
// printf("process: %d %d %d %d\n", p1, p2, n1, n2);
if (!n1 || !n2) break;
if (n1 <= n2) {
for (auto x1: S1) {
auto pt = S2.lower_bound(make_pair(x1.first, 0));
// printf("%d %d %d\n", pt->first, pt->second, x1.first);
if (pt == S2.begin()) {
puts("impossible");
return 0;
}
auto x2 = *(--pt);
// printf("%d %d\n", x2.first, x2.second);
ans1[++k] = x1.second;
ans2[k] = x2.second;
S2.erase(x2);
}
S1.clear();
} else {
for (auto x2: S2) {
auto pt = S1.lower_bound(make_pair(x2.first+1, 0));
if (pt == S1.end()) {
puts("impossible");
return 0;
}
auto x1 = *pt;
ans1[++k] = x1.second;
ans2[k] = x2.second;
S1.erase(x1);
}
S2.clear();
}
if (p1 > n && p2 > n && S1.size() == 0) {
break;
}
if (p1 <= n && S1.size() == 0) {
int st1 = p1;
while (p1<=n && t1[p1].p == t1[st1].p) {
S1.insert(make_pair(t1[p1].h, t1[p1].i));
p1++;
}
}
if (p2 <= n && S2.size() == 0) {
int st2 = p2;
while (p2<=n && t2[p2].p == t2[st2].p) {
S2.insert(make_pair(t2[p2].h, t2[p2].i));
p2++;
}
}
}
for(int i=1;i<=n;i++) {
printf("%d ", ans1[i]);
}
puts("");
for(int i=1;i<=n;i++) {
printf("%d ", ans2[i]);
}
puts("");
return 0;
}
Details
Test #1:
score: 100
Accepted
time: 0ms
memory: 9904kb
Test #2:
score: 0
Accepted
time: 1ms
memory: 5644kb
Test #3:
score: 0
Accepted
time: 1ms
memory: 7976kb
Test #4:
score: 0
Accepted
time: 1ms
memory: 5740kb
Test #5:
score: 0
Accepted
time: 0ms
memory: 10020kb
Test #6:
score: 0
Accepted
time: 0ms
memory: 5740kb
Test #7:
score: 0
Accepted
time: 1ms
memory: 10004kb
Test #8:
score: 0
Accepted
time: 0ms
memory: 9904kb
Test #9:
score: 0
Accepted
time: 1ms
memory: 10096kb
Test #10:
score: 0
Accepted
time: 1ms
memory: 9948kb
Test #11:
score: 0
Accepted
time: 1ms
memory: 10020kb
Test #12:
score: 0
Accepted
time: 298ms
memory: 44004kb
Test #13:
score: 0
Accepted
time: 0ms
memory: 9904kb
Test #14:
score: 0
Accepted
time: 2ms
memory: 9988kb
Test #15:
score: 0
Accepted
time: 6ms
memory: 10612kb
Test #16:
score: 0
Accepted
time: 1ms
memory: 10092kb
Test #17:
score: 0
Accepted
time: 1ms
memory: 10024kb
Test #18:
score: 0
Accepted
time: 1ms
memory: 10028kb
Test #19:
score: 0
Accepted
time: 1ms
memory: 10024kb
Test #20:
score: 0
Accepted
time: 1ms
memory: 9948kb
Test #21:
score: 0
Accepted
time: 1ms
memory: 7804kb
Test #22:
score: 0
Accepted
time: 65ms
memory: 13244kb
Test #23:
score: 0
Accepted
time: 62ms
memory: 16748kb
Test #24:
score: 0
Accepted
time: 72ms
memory: 18136kb
Test #25:
score: 0
Accepted
time: 48ms
memory: 11112kb
Test #26:
score: 0
Accepted
time: 266ms
memory: 44484kb
Test #27:
score: 0
Accepted
time: 55ms
memory: 19200kb
Test #28:
score: 0
Accepted
time: 64ms
memory: 19636kb
Test #29:
score: 0
Accepted
time: 58ms
memory: 15880kb
Test #30:
score: 0
Accepted
time: 45ms
memory: 17792kb
Test #31:
score: 0
Accepted
time: 444ms
memory: 43088kb
Test #32:
score: 0
Accepted
time: 74ms
memory: 17924kb
Test #33:
score: 0
Accepted
time: 396ms
memory: 44300kb