QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#805739 | #2337. Azulejos | SGColin | AC ✓ | 423ms | 44976kb | C++20 | 2.3kb | 2024-12-08 18:16:36 | 2024-12-08 18:16:38 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
inline int rd() {
int x = 0;
bool f = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define pii pair<int, int>
#define tii tuple<int, int, int>
#define N 500007
int p[N], ansb[N], anss[N];
tii b[N], s[N];
set<pii> B, S;
int main() {
int n = rd();
for (int i = 1; i <= n; ++i) p[i] = rd();
for (int i = 1; i <= n; ++i) b[i] = mt(p[i], rd(), i);
sort(b + 1, b + 1 + n);
for (int i = 1; i <= n; ++i) p[i] = rd();
for (int i = 1; i <= n; ++i) s[i] = mt(p[i], rd(), i);
sort(s + 1, s + 1 + n);
int tot = 0;
for (int ptrs = 0, ptrb = 0; ptrs < n || ptrb < n;) {
if (ptrs > ptrb) {
++ptrb;
B.insert(mp(get<1>(b[ptrb]), get<2>(b[ptrb])));
while (ptrb < n && get<0>(b[ptrb]) == get<0>(b[ptrb + 1])) {
++ptrb; B.insert(mp(get<1>(b[ptrb]), get<2>(b[ptrb])));
}
} else if (ptrs < ptrb) {
++ptrs;
S.insert(mp(get<1>(s[ptrs]), get<2>(s[ptrs])));
while (ptrs < n && get<0>(s[ptrs]) == get<0>(s[ptrs + 1])) {
++ptrs; S.insert(mp(get<1>(s[ptrs]), get<2>(s[ptrs])));
}
} else {
++ptrb;
B.insert(mp(get<1>(b[ptrb]), get<2>(b[ptrb])));
while (ptrb < n && get<0>(b[ptrb]) == get<0>(b[ptrb + 1])) {
++ptrb; B.insert(mp(get<1>(b[ptrb]), get<2>(b[ptrb])));
}
++ptrs;
S.insert(mp(get<1>(s[ptrs]), get<2>(s[ptrs])));
while (ptrs < n && get<0>(s[ptrs]) == get<0>(s[ptrs + 1])) {
++ptrs; S.insert(mp(get<1>(s[ptrs]), get<2>(s[ptrs])));
}
}
if (ptrs <= ptrb) {
for (auto [h, id] : S) {
if (h >= (*--B.end()).first) {puts("impossible"); return 0;}
anss[++tot] = id; ansb[tot] = (*B.upper_bound(mp(h, 1e9))).second;
B.erase(B.upper_bound(mp(h, 1e9)));
}
S.clear();
} else {
for (auto [h, id] : B) {
if (h <= (*S.begin()).first) {puts("impossible"); return 0;}
ansb[++tot] = id; anss[tot] = (*--S.lower_bound(mp(h, 0))).second;
S.erase(--S.lower_bound(mp(h, 0)));
}
B.clear();
}
}
for (int i = 1; i <= n; ++i) printf("%d ", ansb[i]); puts("");
for (int i = 1; i <= n; ++i) printf("%d ", anss[i]);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 9932kb
Test #2:
score: 0
Accepted
time: 1ms
memory: 7804kb
Test #3:
score: 0
Accepted
time: 0ms
memory: 12052kb
Test #4:
score: 0
Accepted
time: 1ms
memory: 7760kb
Test #5:
score: 0
Accepted
time: 0ms
memory: 12156kb
Test #6:
score: 0
Accepted
time: 1ms
memory: 7816kb
Test #7:
score: 0
Accepted
time: 1ms
memory: 11996kb
Test #8:
score: 0
Accepted
time: 0ms
memory: 10012kb
Test #9:
score: 0
Accepted
time: 1ms
memory: 12092kb
Test #10:
score: 0
Accepted
time: 0ms
memory: 11704kb
Test #11:
score: 0
Accepted
time: 1ms
memory: 11972kb
Test #12:
score: 0
Accepted
time: 220ms
memory: 44976kb
Test #13:
score: 0
Accepted
time: 0ms
memory: 12156kb
Test #14:
score: 0
Accepted
time: 1ms
memory: 10032kb
Test #15:
score: 0
Accepted
time: 0ms
memory: 12616kb
Test #16:
score: 0
Accepted
time: 0ms
memory: 11976kb
Test #17:
score: 0
Accepted
time: 1ms
memory: 12044kb
Test #18:
score: 0
Accepted
time: 2ms
memory: 12028kb
Test #19:
score: 0
Accepted
time: 0ms
memory: 12100kb
Test #20:
score: 0
Accepted
time: 1ms
memory: 12048kb
Test #21:
score: 0
Accepted
time: 1ms
memory: 11912kb
Test #22:
score: 0
Accepted
time: 46ms
memory: 16908kb
Test #23:
score: 0
Accepted
time: 40ms
memory: 18684kb
Test #24:
score: 0
Accepted
time: 59ms
memory: 19736kb
Test #25:
score: 0
Accepted
time: 30ms
memory: 15220kb
Test #26:
score: 0
Accepted
time: 168ms
memory: 44540kb
Test #27:
score: 0
Accepted
time: 30ms
memory: 19876kb
Test #28:
score: 0
Accepted
time: 49ms
memory: 21536kb
Test #29:
score: 0
Accepted
time: 34ms
memory: 21456kb
Test #30:
score: 0
Accepted
time: 33ms
memory: 19744kb
Test #31:
score: 0
Accepted
time: 423ms
memory: 44820kb
Test #32:
score: 0
Accepted
time: 56ms
memory: 20884kb
Test #33:
score: 0
Accepted
time: 308ms
memory: 44864kb