QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#422974 | #8179. 2D Parentheses | qwqwf | WA | 132ms | 11132kb | C++14 | 1.3kb | 2024-05-27 20:37:49 | 2024-05-27 20:37:49 |
Judging History
answer
#pragma GCC optimize("Ofast","unroll-loops","inline")
#include<bits/stdc++.h>
#define ll long long
//#define int ll
#define pb push_back
#define pii pair<int,int>
#define MP make_pair
#define fi first
#define se second
using namespace std;
const int N=5e5+10,M=1e6+10,mod=998244353;
int n,X[N],Y[N];
int ans[N];
int p[N];
set<pii> st;
multiset<int> s;
inline bool cmp(int a,int b){return X[a]!=X[b]?X[a]>X[b]:Y[a]>Y[b];}
bool solve(){
for(int i=0;i<2*n;i++) p[i]=i;
sort(p,p+2*n,cmp);
for(int i=0;i<2*n;i++){
int v=p[i];
if(v<n){
auto w=st.lower_bound(MP(Y[v],0));
if(w==st.end()) return 0;
int t=(*w).se;
ans[v]=t;ans[t]=v;
st.erase(w);
}
else st.insert(MP(Y[v],v));
}
for(int i=0;i<2*n;i++){
int u=p[i],v=ans[u];
if(u<n) s.erase(s.find(Y[u])),s.erase(s.find(Y[v]));
else{
if(Y[u]<Y[v]) swap(u,v);
auto w=s.lower_bound(Y[u]);
if(w!=s.begin()){
--w;
if((*w)>Y[v]) return 0;
}
s.insert(Y[u]);s.insert(Y[v]);
}
}
return 1;
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n;
for(int i=0;i<n;i++) cin>>X[i]>>Y[i],X[i]*=2,Y[i]*=2;
for(int i=n;i<2*n;i++)cin>>X[i]>>Y[i],X[i]*=2,Y[i]*=2,X[i]--,Y[i]--;
if(!solve()) return cout<<"No\n",0;
else{
cout<<"Yes\n";
for(int i=0;i<n;i++) cout<<ans[i]-n+1<<'\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 9756kb
input:
3 0 0 2 -2 1 1 2 2 3 1 2 3
output:
Yes 3 2 1
result:
ok answer is YES, 3 tokens
Test #2:
score: 0
Accepted
time: 0ms
memory: 9808kb
input:
2 1 0 0 1 2 3 3 2
output:
No
result:
ok answer is NO
Test #3:
score: 0
Accepted
time: 1ms
memory: 7788kb
input:
1 1 1 0 0
output:
No
result:
ok answer is NO
Test #4:
score: -100
Wrong Answer
time: 132ms
memory: 11132kb
input:
199996 94702923 895749121 -830347683 823853414 -638337012 -528381915 774504965 -903560893 465975432 931026841 47062323 901390864 539345338 830099354 278774201 896803047 -445303873 568413124 80473317 828648317 804283391 -307873779 543648687 893783688 814084625 -664894626 169476937 -999435847 -8232728...
output:
No
result:
wrong answer expected YES, found NO