QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#550758 | #2337. Azulejos | RngBased# | AC ✓ | 384ms | 42856kb | C++17 | 2.4kb | 2024-09-07 14:11:42 | 2024-09-07 14:11:43 |
Judging History
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;
}
Details
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