QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#53573 | #2337. Azulejos | not_so_organic | AC ✓ | 685ms | 50664kb | C++11 | 2.4kb | 2022-10-05 13:32:19 | 2022-10-05 13:32:21 |
Judging History
answer
#include <bits/stdc++.h>
#define N 500005
#define Ms(a,b) memset(a,b,sizeof a)
#define db(x) cerr<<#x<<"="<<x<<endl;
#define db2(x,y) cerr<<#x<<"="<<x<<" "<<#y<<"="<<y<<endl;
#define db3(x,y,z) cerr<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl;
using namespace std;
int rd() {
int res = 0, c;
while (c = getchar(), c < 48);
do
res = (res << 1) + (res << 3) + (c ^ 48);
while (c = getchar(), c >= 48);
return res;
}
struct node {
int x, v, h;
bool operator <(const node &b)const {
return h < b.h;
}
} a[N], b[N];
struct cmp {
bool operator()(const node &a, const node &b)const {
return a.v < b.v;
}
};
int n, r1[N], r2[N];
multiset<node>st1, st2;
multiset<node>::iterator it, cur;
int main() {
n = rd();
for (int i = 1; i <= n; i++)
a[i].v = rd();
for (int i = 1; i <= n; i++)
a[i].h = rd(), a[i].x = i;
for (int i = 1; i <= n; i++)
b[i].v = rd();
for (int i = 1; i <= n; i++)
b[i].h = rd(), b[i].x = i;
sort(a + 1, a + 1 + n, cmp());
sort(b + 1, b + 1 + n, cmp());
int s = 1, t1 = 0, t2 = 0;
while (s <= n) {
if (t1 < s) {
st1.insert(a[s]), t1 = s;
while (t1 < n && a[t1].v == a[t1 + 1].v)
st1.insert(a[++t1]);
}
if (t2 < s) {
st2.insert(b[s]), t2 = s;
while (t2 < n && b[t2].v == b[t2 + 1].v)
st2.insert(b[++t2]);
}
if (t1 <= t2) {
for (cur = st1.begin(); cur != st1.end(); cur++) {
it = st2.lower_bound(*cur);
if (it == st2.begin())
return puts("impossible"), 0;
else
it--;
r1[s] = cur->x, r2[s] = it->x, ++s;
st2.erase(it);
}
st1.clear();
} else {
for (cur = st2.begin(); cur != st2.end(); cur++) {
it = st1.upper_bound(*cur);
if (it == st1.end())
return puts("impossible"), 0;
r1[s] = it->x, r2[s] = cur->x, ++s;
st1.erase(it);
}
st2.clear();
}
}
for (int i = 1; i <= n; i++)
printf("%d%c", r1[i], " \n"[i == n]);
for (int i = 1; i <= n; i++)
printf("%d%c", r2[i], " \n"[i == n]);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 5764kb
Test #2:
score: 0
Accepted
time: 3ms
memory: 5620kb
Test #3:
score: 0
Accepted
time: 2ms
memory: 5812kb
Test #4:
score: 0
Accepted
time: 2ms
memory: 5692kb
Test #5:
score: 0
Accepted
time: 2ms
memory: 5692kb
Test #6:
score: 0
Accepted
time: 3ms
memory: 5624kb
Test #7:
score: 0
Accepted
time: 2ms
memory: 5768kb
Test #8:
score: 0
Accepted
time: 2ms
memory: 5708kb
Test #9:
score: 0
Accepted
time: 2ms
memory: 5712kb
Test #10:
score: 0
Accepted
time: 2ms
memory: 5576kb
Test #11:
score: 0
Accepted
time: 2ms
memory: 5640kb
Test #12:
score: 0
Accepted
time: 275ms
memory: 50664kb
Test #13:
score: 0
Accepted
time: 2ms
memory: 5696kb
Test #14:
score: 0
Accepted
time: 3ms
memory: 5716kb
Test #15:
score: 0
Accepted
time: 8ms
memory: 6508kb
Test #16:
score: 0
Accepted
time: 0ms
memory: 5780kb
Test #17:
score: 0
Accepted
time: 2ms
memory: 5692kb
Test #18:
score: 0
Accepted
time: 2ms
memory: 5748kb
Test #19:
score: 0
Accepted
time: 1ms
memory: 5696kb
Test #20:
score: 0
Accepted
time: 3ms
memory: 5856kb
Test #21:
score: 0
Accepted
time: 2ms
memory: 5644kb
Test #22:
score: 0
Accepted
time: 53ms
memory: 8348kb
Test #23:
score: 0
Accepted
time: 74ms
memory: 13136kb
Test #24:
score: 0
Accepted
time: 84ms
memory: 12604kb
Test #25:
score: 0
Accepted
time: 50ms
memory: 7656kb
Test #26:
score: 0
Accepted
time: 144ms
memory: 50324kb
Test #27:
score: 0
Accepted
time: 54ms
memory: 14688kb
Test #28:
score: 0
Accepted
time: 54ms
memory: 13980kb
Test #29:
score: 0
Accepted
time: 45ms
memory: 14244kb
Test #30:
score: 0
Accepted
time: 36ms
memory: 14608kb
Test #31:
score: 0
Accepted
time: 685ms
memory: 50592kb
Test #32:
score: 0
Accepted
time: 70ms
memory: 14588kb
Test #33:
score: 0
Accepted
time: 576ms
memory: 50520kb