QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#864989#9975. Hitoshizukupsc233WA 54ms8016kbC++141.2kb2025-01-21 13:06:172025-01-21 13:06:17

Judging History

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

  • [2025-01-21 13:06:17]
  • 评测
  • 测评结果:WA
  • 用时:54ms
  • 内存:8016kb
  • [2025-01-21 13:06:17]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
int a[N],b[N],q[N],p[N],tag[N];
int T,n;
bool cmp1(int x,int y){
	return a[x]<a[y];
}
bool cmp2(int x,int y){
	return b[x]<b[y];
}
int main(){
	scanf("%d",&T);
	while (T--){
		scanf("%d",&n);
		for (int i=1;i<=n*3;i++){
			scanf("%d%d",&a[i],&b[i]);
			q[i]=i; p[i]=i;
		}
		sort(q+1,q+n*3+1,cmp1);
		sort(p+1,p+n*3+1,cmp2);
		for (int i=1;i<=n*3;i++) tag[i]=0;
		vector<pair<int,pair<int,int>>>ans;
		priority_queue<int,vector<int>,decltype(&cmp2)>qp(cmp2);
		int id=1;
		for (int i=1;i<=n*3;i++){
			if (tag[p[i]]) continue;
			tag[p[i]]=1;
			pair<int,int>w;
			for (;id<=n*3&&a[q[id]]<=b[p[i]];id++){
				if (tag[q[id]]) continue;
				qp.push(q[id]);
			}
			int sum=2;
			while (!qp.empty()&&sum){
				int t=qp.top(); qp.pop();
				if (tag[t]) continue;
				tag[t]=1;
				if (sum==2) w.first=t; else w.second=t;
				sum--;
			}
			if (sum) break;
			ans.push_back(make_pair(p[i],w));
		} 
		if (ans.size()==n){
			puts("Yes");
			for (int i=0;i<ans.size();i++) printf("%d %d %d\n",ans[i].first,ans[i].second.first,ans[i].second.second);
		}else puts("No");
	}
} 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 8016kb

input:

2
2
1 2
2 2
2 3
3 5
4 4
4 5
1
1 1
1 1000000000
1000000000 1000000000

output:

Yes
1 3 2
5 4 6
No

result:

ok >_< (2 test cases)

Test #2:

score: 0
Accepted
time: 54ms
memory: 8016kb

input:

100000
1
164154503 167959139
178382610 336470888
12298535 642802746
1
165064830 773386884
353585658 396628655
792066242 971207868
1
1607946 2087506
21674839 46761498
9518201 16843338
1
262361007 691952768
190585553 787375312
637191526 693319712
1
41970708 45277106
197619816 762263554
308360206 40724...

output:

No
No
No
Yes
1 2 3
No
Yes
2 3 1
No
No
No
No
No
Yes
2 3 1
Yes
1 3 2
No
No
No
No
Yes
2 1 3
No
Yes
2 1 3
No
No
Yes
2 1 3
No
No
Yes
3 2 1
No
No
No
No
No
No
No
Yes
3 1 2
No
No
Yes
3 1 2
No
No
No
No
No
No
No
No
No
No
No
No
Yes
3 1 2
No
No
Yes
2 1 3
Yes
3 1 2
No
No
Yes
2 3 1
No
No
No
Yes
1 3 2
Yes
3 1 2
No...

result:

ok >_< (100000 test cases)

Test #3:

score: -100
Wrong Answer
time: 53ms
memory: 8012kb

input:

50000
2
36364670 641009859
15071436 75475634
20446080 476927808
357784519 503158867
206641725 322595515
268011721 645468307
2
247717926 939887597
808609669 973764525
496738491 710156469
463547010 860350786
757388873 784695957
29903136 208427221
2
26681139 67590963
458238185 475357775
80127817 135993...

output:

No
No
No
No
No
No
No
No
No
No
No
No
Yes
5 1 3
4 2 6
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
2 3 6
1 5 4
No
No
No
Yes
3 6 1
4 5 2
No
No
Yes
6 4 3
1 2 5
Yes
2 6 5
1 3 4
No
No
Yes
4 3 6
5 1 2
No
No
No
No
Yes
3 2 5
1 4 6
No
No
No
No
No
Yes
2 1 4
3...

result:

wrong answer There is a valid answer, but participant did not find it. (test case 30)