QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#422974#8179. 2D ParenthesesqwqwfWA 132ms11132kbC++141.3kb2024-05-27 20:37:492024-05-27 20:37:49

Judging History

你现在查看的是最新测评结果

  • [2024-05-27 20:37:49]
  • 评测
  • 测评结果:WA
  • 用时:132ms
  • 内存:11132kb
  • [2024-05-27 20:37:49]
  • 提交

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