QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#422907#8179. 2D Parenthesesjr_linysWA 1ms7788kbC++141.4kb2024-05-27 20:09:572024-05-27 20:09:57

Judging History

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

  • [2024-05-27 20:09:57]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:7788kb
  • [2024-05-27 20:09:57]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
template<typename T=int> T read(){
	char c;bool f=1;
	while(!isdigit(c=getchar())) if(c=='-') f=0;
	T x=c^'0';
	while(isdigit(c=getchar())) x=x*10+(c^'0');
	return f?x:-x;
}
template<class T>void Min(T &a,T b){if(b<a) a=b;}
template<class T>void Max(T &a,T b){if(b>a) a=b;}
const int N=200000;
int n,un[N*2+5],ans[N+5];
struct Dot{
	int x,y,id;
}a[N+5],b[N+5];
struct cmp{
	bool operator()(int u,int v)const{
		return a[u].y<a[v].y||(a[u].y==a[v].y&&a[u].x<a[v].x);
	}
};
set<int,cmp> T;

signed main(){
	{//预处理
		n=read();
		for(int i=1;i<=n;++i) a[i]={read(),read(),i};
		for(int i=1;i<=n;++i) b[i]={read(),read(),i};
		auto get=[](int &x){x=lower_bound(un+1,un+1+n*2,x)-un;};
		for(int i=1;i<=n;++i) un[i]=a[i].x,un[i+n]=b[i].x;
		sort(un+1,un+1+n*2);
		for(int i=1;i<=n;++i) get(a[i].x),get(b[i].x);
		for(int i=1;i<=n;++i) un[i]=a[i].y,un[i+n]=b[i].y;
		sort(un+1,un+1+n*2);
		for(int i=1;i<=n;++i) get(a[i].y),get(b[i].y);
	}
	sort(a+1,a+1+n,[](Dot a,Dot b){return a.x<b.x;});
	sort(b+1,b+1+n,[](Dot a,Dot b){return a.x<b.x||(a.x==b.x&&a.y<b.y);});
	for(int i=1,j=1;i<=n;++i){
		while(j<=n&&a[j].x<b[i].x) T.insert(j),++j;
		a[0]=b[i];
		if(T.empty()){printf("No"); return 0;}
		auto it=--T.upper_bound(0);
		ans[a[*it].id]=b[i].id;
		T.erase(it);
	}
	cout<<"Yes\n";
	for(int i=1;i<=n;++i) cout<<ans[i]<<'\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 7696kb

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: -100
Wrong Answer
time: 1ms
memory: 7788kb

input:

2
1 0
0 1
2 3
3 2

output:

Yes
2
1

result:

wrong answer expected NO, found YES