QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#478187#2345. Karel the RobotkarunaWA 1ms5884kbC++172.4kb2024-07-14 18:25:472024-07-14 18:25:47

Judging History

This is the latest submission verdict.

  • [2024-07-14 18:25:47]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 5884kb
  • [2024-07-14 18:25:47]
  • Submitted

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