QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#478187 | #2345. Karel the Robot | karuna | WA | 1ms | 5884kb | C++17 | 2.4kb | 2024-07-14 18:25:47 | 2024-07-14 18:25:47 |
Judging History
answer
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int SZ = 505050;
int n, a[SZ], b[SZ], c[SZ], d[SZ];
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) cin >> b[i];
for (int i = 0; i < n; i++) cin >> c[i];
for (int i = 0; i < n; i++) cin >> d[i];
int ord_a[n], ord_b[n];
iota(ord_a, ord_a + n, 0);
sort(ord_a, ord_a + n, [&](int i, int j) {
return a[i] < a[j];
});
iota(ord_b, ord_b + n, 0);
sort(ord_b, ord_b + n, [&](int i, int j) {
return c[i] < c[j];
});
queue<set<pii>> Q[2];
vector<int> ans_a, ans_b;
for (int i = 0, p = 0; i < n; i = p) {
set<pii> st;
while (p < n && a[ord_a[i]] == a[ord_a[p]]) {
st.insert({b[ord_a[p]], ord_a[p]});
++p;
}
Q[0].push(st);
}
for (int i = 0, p = 0; i < n; i = p) {
set<pii> st;
while (p < n && c[ord_b[i]] == c[ord_b[p]]) {
st.insert({d[ord_b[p]], ord_b[p]});
++p;
}
Q[1].push(st);
}
while (!Q[0].empty() && !Q[1].empty()) {
auto &S = Q[0].front();
auto &T = Q[1].front();
if (S.size() < T.size()) {
for (auto [x, pos] : S) {
auto it = T.lower_bound({x, -1});
if (it == T.begin()) {
return !(cout << "impossible\n");
}
ans_a.push_back(pos);
ans_b.push_back(prev(it)->ss);
T.erase(prev(it));
}
Q[0].pop();
if (Q[1].front().empty()) Q[1].pop();
}
else {
for (auto [x, pos] : T) {
auto it = S.upper_bound({x, 1e9});
if (it == S.end()) {
return !(cout << "impossible\n");
}
ans_a.push_back(it->ss);
ans_b.push_back(pos);
S.erase(it);
}
Q[1].pop();
if (Q[0].front().empty()) Q[0].pop();
}
}
for (int x : ans_a) cout << x + 1 << ' '; cout << '\n';
for (int x : ans_b) cout << x + 1 << ' '; cout << '\n';
}
Details
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 5884kb