QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#262108#5423. Perfect Matchingvp_accountWA 206ms25980kbC++141.4kb2023-11-23 15:37:202023-11-23 15:37:21

Judging History

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

  • [2023-11-23 15:37:21]
  • 评测
  • 测评结果:WA
  • 用时:206ms
  • 内存:25980kb
  • [2023-11-23 15:37:20]
  • 提交

answer

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
using namespace std;
constexpr int N=2e5+5;
int a[N],dep[N];
vector<pair<int,int>>G[N];
unordered_map<int,int>id1,id2;
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int T;
	cin>>T;
	while(T--)
	{
		int n,idx=0;
		cin>>n,id1.clear(),id2.clear();
		rep(i,1,n)
		{
			cin>>a[i];
			if(!id1[i-a[i]])id1[i-a[i]]=++idx;
			if(!id2[i+a[i]])id2[i+a[i]]=++idx;
			G[id1[i-a[i]]].emplace_back(id2[i+a[i]],i);
			G[id2[i+a[i]]].emplace_back(id1[i-a[i]],i);
		}
		vector<pair<int,int>>ans;
		auto dfs=[&](int x,int fa,auto dfs)->int
		{
			vector<int>edges;
			dep[x]=dep[fa]+1;
			for(auto[y,id]:G[x])
			{
				if(!dep[y])
				{
					int w=dfs(y,x,dfs);
					if(w)ans.emplace_back(id,w);
					else edges.emplace_back(id);
				}
				else if(dep[y]>dep[x])edges.emplace_back(id);
			}
			int pm=(int)edges.size()>>1;
			rep(i,0,pm-1)ans.emplace_back(edges[i<<1],edges[i<<1|1]);
			return (int)edges.size()&1?edges[pm<<1]:0;
		};
		rep(i,1,idx)if(!dep[i])dfs(i,0,dfs);
		if(ans.size()==(n>>1))
		{
			cout<<"Yes\n";
			for(auto[x,y]:ans)cout<<x<<' '<<y<<'\n';
		}
		else cout<<"No\n";
		rep(i,1,1000)dep[i]=0,G[i].clear();
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 9636kb

input:

3
6
14 22 33 11 25 36
4
100 10 98 12
4
1 3 5 7

output:

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

result:

ok 3 Cases (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 206ms
memory: 25980kb

input:

10
100000
0 -1 -2 -3 -4 -5 -2 -7 -8 -9 -10 -9 -12 13 14 15 -16 -17 -18 19 20 19 -22 -21 -20 -25 -26 -27 -28 -27 -26 31 30 29 -34 -35 -34 39 38 37 42 41 42 47 44 45 46 49 48 -53 -52 -51 -56 -55 -54 55 56 57 -58 -59 -60 61 62 63 64 65 64 67 66 69 70 73 72 73 74 73 76 75 74 79 80 81 -84 -83 -84 89 86 8...

output:

Yes
79 139
202 244
289 310
316 322
337 382
397 451
460 463
481 517
520 526
556 568
619 661
736 763
790 853
904 934
979 988
1090 1105
1162 1219
1273 1285
1294 1405
1411 1456
1459 1531
1555 1561
1588 1615
1618 1630
1651 1669
1684 1723
1738 1915
1972 2026
2029 2092
2155 2197
2290 2305
2350 2353
2419 24...

result:

wrong answer std outputs a valid answer while participant doesn't (test case 2)