QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#60113 | #2337. Azulejos | captured | AC ✓ | 545ms | 41816kb | C++17 | 4.5kb | 2022-11-02 21:35:23 | 2022-11-02 21:35:25 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
const int maxn = 5e5+5;
struct D {
int p, h, idx;
} bck[maxn], frnt[maxn], X[maxn], Y[maxn];
bool cmp(const D &a, const D &b) {
if (a.p == b.p) {
return a.h < b.h;
}
return a.p < b.p;
}
bool cmp2 (const pair<int, pair<int, int>> a, const pair<int, pair<int, int>> b) {
if (X[a.second.first].p == X[b.second.first].p) {
return Y[a.second.second].p < Y[b.second.second].p;
}
return X[a.second.first].p < X[b.second.first].p;
}
void solve(int cs){
int n, x;
cin>>n;
for (int i = 1; i <= n; i++) {
cin>>x;
bck[i].p = x;
}
for (int i = 1; i <= n; i++) {
cin>>x;
bck[i].h = x;
bck[i].idx = i;
}
for (int i = 1; i <= n; i++) {
cin>>x;
frnt[i].p = x;
}
for (int i = 1; i <= n; i++) {
cin>>x;
frnt[i].h = x;
frnt[i].idx = i;
}
sort(frnt+1, frnt+n+1, cmp);
sort(bck+1, bck+n+1, cmp);
int f = 0, j = 1;
// map<int, multiset<pair<int, int>>> mp, mp2;
//
// for (int i = 1; i <= n; i++) {
// mp[bck[i].p].insert({bck[i].h, bck[i].idx});
// }
// for (int i = 1; i <= n; i++) {
// mp2[frnt[i].p].insert({frnt[i].h, frnt[i].idx});
// }
// auto bc = mp.begin(), fr = mp2.begin();
// vector<pair<int, int>> ans;
// while (bc != mp.end() && fr != mp2.end()) {
// vector<pair<int, int> > tmp;
// for (auto x: fr.first) {
// if (bc.first.upper_bound(x.first) != bc.first.end()) {
// bc.first.erase()
// }
// }
// }
queue<pair<int, int > >st;
int pointerr = 1;
int pointerr2 = 1;
multiset <pair <int, int> >mp, mp2;
vector<int> ans1 ,ans2;
for(int i = 1; i <= n; i++)
{
if(mp2.empty())
{
int j = pointerr;
while(j <= n)
{
if(bck[j].p == bck[pointerr].p)
{
mp2.insert({bck[j].h , bck[j].idx});
j++;
}
else
break;
}
pointerr = j;
}
if(mp.empty())
{
int j = pointerr2;
while(j <= n)
{
if(frnt[j].p == frnt[pointerr2].p)
{
mp.insert({frnt[j].h , frnt[j].idx});
j++;
}
else
break;
}
pointerr2 = j;
}
auto tmp_f = mp2.begin();
int val = (*tmp_f).first;
auto it = mp.lower_bound({val, 0});
// for(auto mp_x : mp)
// {
// cout << mp_x.first << " -> " << mp_x.second << endl;
// }
// cout << " for " << i << endl;
// cout << "searhinf " << val << " " <<(*it).first<<endl;
if(it == mp.begin())
{
auto tmp_f2 = mp.begin();
val = (*tmp_f2).first;
auto it2 = mp2.upper_bound({val, 1e9+7});
// for(auto mp_x : mp)
// {
// cout << mp_x.first << " -> " << mp_x.second << endl;
// }
// cout << " for " << i << endl;
// cout << "searhinf " << val << " " <<(*it).first<<endl;
if(it2 == mp2.end())
{
f = 1;
break;
}
// cout << "searhinf " << val << " " <<(*it).first<<endl;
ans2.push_back((*tmp_f2).second);
ans1.push_back((*it2).second);
mp2.erase(it2);
mp.erase(mp.begin());
}
else {
it--;
// cout << "searhinf " << val << " " <<(*it).first<<endl;
if((*it).first >= val)
assert(0);
ans1.push_back((*tmp_f).second);
ans2.push_back((*it).second);
mp.erase(it);
mp2.erase(mp2.begin());
}
}
if(f)
{
cout << "impossible" << endl;
}
else
{
for(auto x : ans1)
{
cout << x << " ";
}
cout << endl;
for(auto x : ans2)
{
cout << x << " ";
}
cout << endl;
}
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int t;t=1;
//cin>>t;
for(int cs=1;cs<=t;cs++)solve(cs);
return 0;
}
Details
Test #1:
score: 100
Accepted
time: 0ms
memory: 7668kb
Test #2:
score: 0
Accepted
time: 1ms
memory: 7624kb
Test #3:
score: 0
Accepted
time: 2ms
memory: 7744kb
Test #4:
score: 0
Accepted
time: 3ms
memory: 7720kb
Test #5:
score: 0
Accepted
time: 2ms
memory: 7660kb
Test #6:
score: 0
Accepted
time: 3ms
memory: 7664kb
Test #7:
score: 0
Accepted
time: 2ms
memory: 7624kb
Test #8:
score: 0
Accepted
time: 0ms
memory: 7644kb
Test #9:
score: 0
Accepted
time: 3ms
memory: 7720kb
Test #10:
score: 0
Accepted
time: 2ms
memory: 7620kb
Test #11:
score: 0
Accepted
time: 3ms
memory: 7744kb
Test #12:
score: 0
Accepted
time: 376ms
memory: 40204kb
Test #13:
score: 0
Accepted
time: 2ms
memory: 7776kb
Test #14:
score: 0
Accepted
time: 2ms
memory: 7712kb
Test #15:
score: 0
Accepted
time: 4ms
memory: 8192kb
Test #16:
score: 0
Accepted
time: 4ms
memory: 7624kb
Test #17:
score: 0
Accepted
time: 3ms
memory: 7640kb
Test #18:
score: 0
Accepted
time: 2ms
memory: 7748kb
Test #19:
score: 0
Accepted
time: 3ms
memory: 7612kb
Test #20:
score: 0
Accepted
time: 2ms
memory: 7844kb
Test #21:
score: 0
Accepted
time: 3ms
memory: 7820kb
Test #22:
score: 0
Accepted
time: 75ms
memory: 12500kb
Test #23:
score: 0
Accepted
time: 71ms
memory: 16164kb
Test #24:
score: 0
Accepted
time: 92ms
memory: 15944kb
Test #25:
score: 0
Accepted
time: 55ms
memory: 12376kb
Test #26:
score: 0
Accepted
time: 334ms
memory: 40376kb
Test #27:
score: 0
Accepted
time: 43ms
memory: 16432kb
Test #28:
score: 0
Accepted
time: 82ms
memory: 16528kb
Test #29:
score: 0
Accepted
time: 68ms
memory: 16396kb
Test #30:
score: 0
Accepted
time: 46ms
memory: 16448kb
Test #31:
score: 0
Accepted
time: 545ms
memory: 41816kb
Test #32:
score: 0
Accepted
time: 93ms
memory: 16452kb
Test #33:
score: 0
Accepted
time: 454ms
memory: 40224kb