QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#531728#2337. AzulejosSwarthmore#WA 1ms3840kbC++142.5kb2024-08-24 21:56:172024-08-24 21:56:19

Judging History

This is the latest submission verdict.

  • [2024-08-24 21:56:19]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3840kb
  • [2024-08-24 21:56:17]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;

struct rec {
    int p, h;
    int id;
    bool operator<(const rec & r) const {
        if (p != r.p) return p < r.p;
        return h < r.h;
    }
};

int main() {
    int n;
    cin >> n;
    vector<rec> a(n), b(n);
    vector<int> pa(n), pb(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i].p;
        pa[i] = a[i].p;
        a[i].id = i;
    }
    for (int i = 0; i < n; i++) {
        cin >> a[i].h;
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i].p;
        pb[i] = b[i].p;
        b[i].id = i;
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i].h;
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    vector<int> ansa(n), ansb(n);
    int i = 0, j = 0;
    set<pair<int, int>> ah, bh;
    unordered_map<int, int> bl;
    int ct = 0;
    for (int i = 0; i < n; i++) {
        if (bl.find(b[i].p) == bl.end()) {
            bl[b[i].p] = i;
        }
    }
    while (ct < n) {
        // Add all with price equal to current a[i]
        int cura = a[i].p;
        while (i < n && a[i].p == cura) {
            ah.insert({a[i].h, a[i].id});
            i++;
        }
        int bp = b[i-1].p;
        while (j < n && b[j].p < bp) {
            bh.insert({b[j].h, b[j].id});
            j++;
        }
        // Add those equal to b[j].p later, we must match them
        for (auto [h, id] : bh) {
            auto it = ah.upper_bound({h, n});
            if (it == ah.end()) {
                cout << "impossible\n";
                return 0;
            }
            ansa[bl[pb[id]]] = it->second;
            ansb[bl[pb[id]]] = id;
            bl[pb[id]]++;
            ct++;
            ah.erase(it);
        }    
        bh.clear();
        while (j < n && b[j].p == bp) {
            bh.insert({b[j].h, b[j].id});
            j++;
        }
        for (auto [h, id] : ah) {
            auto it = bh.lower_bound({h, -1});
            if (it == bh.begin()) {
                cout << "impossible\n";
                return 0;
            }
            it--;
            ansa[bl[bp]] = id;
            ansb[bl[bp]] = it->second;
            bl[bp]++;
            ct++;
            bh.erase(it);
        }
        ah.clear();
    }
    for (int i = 0; i < n; i++) {
        cout << ansa[i] + 1 << " ";
    }
    cout << endl;
    for (int i = 0; i < n; i++) {
        cout << ansb[i] + 1 << " ";
    }
    cout << endl;
}

Details

Test #1:

score: 100
Accepted
time: 1ms
memory: 3644kb

Test #2:

score: 0
Accepted
time: 1ms
memory: 3840kb

Test #3:

score: 0
Accepted
time: 1ms
memory: 3544kb

Test #4:

score: 0
Accepted
time: 1ms
memory: 3556kb

Test #5:

score: 0
Accepted
time: 1ms
memory: 3584kb

Test #6:

score: 0
Accepted
time: 1ms
memory: 3780kb

Test #7:

score: 0
Accepted
time: 1ms
memory: 3780kb

Test #8:

score: -100
Wrong Answer
time: 0ms
memory: 3500kb