QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#550758#2337. AzulejosRngBased#AC ✓384ms42856kbC++172.4kb2024-09-07 14:11:422024-09-07 14:11:43

Judging History

This is the latest submission verdict.

  • [2024-09-07 14:11:43]
  • Judged
  • Verdict: AC
  • Time: 384ms
  • Memory: 42856kb
  • [2024-09-07 14:11:42]
  • Submitted

answer

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
#define F first
#define S second
#define all(x) x.begin(), x.end()
using namespace std;

int n, ford[500005], bord[500005];
pii fr[500005], ba[500005];
int sol[500005][2];

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> ba[i].F;
    for (int i = 1; i <= n; i++)
        cin >> ba[i].S;
    for (int i = 1; i <= n; i++)
        cin >> fr[i].F;
    for (int i = 1; i <= n; i++)
        cin >> fr[i].S; 
    iota(ford, ford + 1 + n, 0);
    sort(ford + 1, ford + 1 + n, [&](int i, int j) { return fr[i] < fr[j]; });
    iota(bord, bord + 1 + n, 0);
    sort(bord + 1, bord + 1 + n, [&](int i, int j) { return ba[i] < ba[j]; });
    multiset<pii, greater<pii>> fst;
    multiset<pii> bst;
    int idx = 1, jdx = 1;
    for (int i = 1; i <= n; )
    {
        if (idx == i)
        {
            int p = fr[ford[idx]].F;
            while (idx <= n && fr[ford[idx]].F == p)
                fst.insert(pii(fr[ford[idx]].S, ford[idx])), ++idx;
        }
        if (jdx == i)
        {
            int p = ba[bord[jdx]].F;
            while (jdx <= n && ba[bord[jdx]].F == p)
                bst.insert(pii(ba[bord[jdx]].S, bord[jdx])), ++jdx;
        }
        if (fst.size() <= bst.size())
        {
            for (auto [f, fi] : fst)
            {
                auto bter = bst.lower_bound(pii(f, n + 1));
                if (bter == bst.end()) goto fail;
                sol[i][0] = bter->S;
                sol[i][1] = fi;
                bst.erase(bter);
                i++;
            }
            fst.clear();
        }
        else 
        {
            for (auto [b, bi] : bst)
            {
                auto fter = fst.lower_bound(pii(b, 0));
                if (fter == fst.end()) goto fail;
                sol[i][0] = bi;
                sol[i][1] = fter->S;
                fst.erase(fter);
                i++;
            }
            bst.clear();
        }
    }
    for (int i = 1; i <= n; i++)
        cout << sol[i][0] << " \n"[i == n];
    for (int i = 1; i <= n; i++)
        cout << sol[i][1] << " \n"[i == n];

    return 0;
    fail:
    cout << "impossible\n";
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 11752kb

Test #2:

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

Test #3:

score: 0
Accepted
time: 0ms
memory: 11816kb

Test #4:

score: 0
Accepted
time: 2ms
memory: 11684kb

Test #5:

score: 0
Accepted
time: 0ms
memory: 11728kb

Test #6:

score: 0
Accepted
time: 2ms
memory: 11816kb

Test #7:

score: 0
Accepted
time: 0ms
memory: 11824kb

Test #8:

score: 0
Accepted
time: 0ms
memory: 11800kb

Test #9:

score: 0
Accepted
time: 2ms
memory: 11812kb

Test #10:

score: 0
Accepted
time: 2ms
memory: 11796kb

Test #11:

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

Test #12:

score: 0
Accepted
time: 237ms
memory: 42856kb

Test #13:

score: 0
Accepted
time: 2ms
memory: 11800kb

Test #14:

score: 0
Accepted
time: 2ms
memory: 12012kb

Test #15:

score: 0
Accepted
time: 2ms
memory: 12364kb

Test #16:

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

Test #17:

score: 0
Accepted
time: 2ms
memory: 11776kb

Test #18:

score: 0
Accepted
time: 0ms
memory: 11792kb

Test #19:

score: 0
Accepted
time: 2ms
memory: 11808kb

Test #20:

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

Test #21:

score: 0
Accepted
time: 0ms
memory: 11808kb

Test #22:

score: 0
Accepted
time: 47ms
memory: 12532kb

Test #23:

score: 0
Accepted
time: 48ms
memory: 18264kb

Test #24:

score: 0
Accepted
time: 65ms
memory: 16540kb

Test #25:

score: 0
Accepted
time: 37ms
memory: 17956kb

Test #26:

score: 0
Accepted
time: 218ms
memory: 42552kb

Test #27:

score: 0
Accepted
time: 42ms
memory: 19284kb

Test #28:

score: 0
Accepted
time: 54ms
memory: 23060kb

Test #29:

score: 0
Accepted
time: 38ms
memory: 20920kb

Test #30:

score: 0
Accepted
time: 33ms
memory: 15820kb

Test #31:

score: 0
Accepted
time: 384ms
memory: 42556kb

Test #32:

score: 0
Accepted
time: 68ms
memory: 17264kb

Test #33:

score: 0
Accepted
time: 348ms
memory: 42620kb