QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#94709 | #2337. Azulejos | DaiRuiChen007 | AC ✓ | 1344ms | 110716kb | C++14 | 1.4kb | 2023-04-07 15:55:40 | 2023-04-07 15:55:40 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+1;
struct node {
int q,h,id;
inline friend bool operator <(const node &A,const node &B) {
if(A.h==B.h) return A.id<B.id;
return A.h<B.h;
}
node(int _q=0,int _h=0,int _id=0): q(_q),h(_h),id(_id) {}
} a[MAXN],b[MAXN];
int s[MAXN],t[MAXN];
set <node> A,B;
map <int,vector<node>> C,D;
signed main() {
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i].q),a[i].id=i;
for(int i=1;i<=n;++i) scanf("%d",&a[i].h),C[a[i].q].push_back(a[i]);
for(int i=1;i<=n;++i) scanf("%d",&b[i].q),b[i].id=i;
for(int i=1;i<=n;++i) scanf("%d",&b[i].h),D[b[i].q].push_back(b[i]);
auto it1=C.begin(),it2=D.begin();
for(int i=1;i<=n;++i) {
if(A.empty()) {
for(auto x:it1->second) A.insert(x);
++it1;
}
if(B.empty()) {
for(auto x:it2->second) B.insert(x);
++it2;
}
if(A.size()<B.size()) {
auto x=A.begin();
auto y=B.upper_bound(node(0,x->h-1,n+1));
if(y==B.begin()) { puts("impossible"); return 0; }
--y;
s[i]=x->id,t[i]=y->id;
A.erase(x),B.erase(y);
} else {
auto y=B.begin();
auto x=A.lower_bound(node(0,y->h+1,0));
if(x==A.end()) { puts("impossible"); return 0; }
s[i]=x->id,t[i]=y->id;
A.erase(x),B.erase(y);
}
}
for(int i=1;i<=n;++i) printf("%d ",s[i]); puts("");
for(int i=1;i<=n;++i) printf("%d ",t[i]); puts("");
return 0;
}
Details
Test #1:
score: 100
Accepted
time: 0ms
memory: 17228kb
Test #2:
score: 0
Accepted
time: 1ms
memory: 16536kb
Test #3:
score: 0
Accepted
time: 6ms
memory: 18072kb
Test #4:
score: 0
Accepted
time: 6ms
memory: 16984kb
Test #5:
score: 0
Accepted
time: 2ms
memory: 18792kb
Test #6:
score: 0
Accepted
time: 0ms
memory: 15444kb
Test #7:
score: 0
Accepted
time: 7ms
memory: 18580kb
Test #8:
score: 0
Accepted
time: 1ms
memory: 17472kb
Test #9:
score: 0
Accepted
time: 6ms
memory: 18648kb
Test #10:
score: 0
Accepted
time: 0ms
memory: 18752kb
Test #11:
score: 0
Accepted
time: 3ms
memory: 18784kb
Test #12:
score: 0
Accepted
time: 565ms
memory: 110716kb
Test #13:
score: 0
Accepted
time: 0ms
memory: 18300kb
Test #14:
score: 0
Accepted
time: 3ms
memory: 19152kb
Test #15:
score: 0
Accepted
time: 14ms
memory: 19944kb
Test #16:
score: 0
Accepted
time: 2ms
memory: 17640kb
Test #17:
score: 0
Accepted
time: 1ms
memory: 17260kb
Test #18:
score: 0
Accepted
time: 1ms
memory: 18716kb
Test #19:
score: 0
Accepted
time: 3ms
memory: 18568kb
Test #20:
score: 0
Accepted
time: 1ms
memory: 17420kb
Test #21:
score: 0
Accepted
time: 0ms
memory: 17728kb
Test #22:
score: 0
Accepted
time: 80ms
memory: 21548kb
Test #23:
score: 0
Accepted
time: 81ms
memory: 24784kb
Test #24:
score: 0
Accepted
time: 109ms
memory: 25792kb
Test #25:
score: 0
Accepted
time: 83ms
memory: 25056kb
Test #26:
score: 0
Accepted
time: 508ms
memory: 110516kb
Test #27:
score: 0
Accepted
time: 102ms
memory: 36804kb
Test #28:
score: 0
Accepted
time: 153ms
memory: 36024kb
Test #29:
score: 0
Accepted
time: 118ms
memory: 36984kb
Test #30:
score: 0
Accepted
time: 83ms
memory: 35900kb
Test #31:
score: 0
Accepted
time: 1344ms
memory: 110468kb
Test #32:
score: 0
Accepted
time: 173ms
memory: 36968kb
Test #33:
score: 0
Accepted
time: 1294ms
memory: 110564kb