QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#106453#5423. Perfect MatchingcokleRE 1ms8160kbC++111.2kb2023-05-17 20:08:422023-05-17 20:08:47

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-17 20:08:47]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:8160kb
  • [2023-05-17 20:08:42]
  • 提交

answer

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10, M = 3e6 + 10;

int n;
int a[N];
int h[N], e[M], ne[M], idx;
int match[N];
bool st[N];

void add(int a, int b)
{
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

bool find(int u)
{
	for(int i=h[u]; i!=-1; i=ne[i])
	{
		int j = e[i];
		if(!st[j])
		{
			st[j] = true;
			if(match[j] == 0 || find(match[j]))
			{
				match[j] = u;
				return true;
			}
		}
	}
	
	return false;
}

int main()
{
	int T;
	scanf("%d", &T);
	while(T -- )
	{
		memset(h, -1, sizeof h);
		memset(match, 0, sizeof match);
		idx = 0;
		
		scanf("%d", &n);
		for(int i=1; i<=n; i++)
			scanf("%d", &a[i]);

		for(int i=1; i<=n; i++)
			for(int j=i+1; j<=n; j++)
			{
				if(abs(i-j)==abs(a[i]-a[j]))
					add(i, j), add(j, i);
			}

		int cnt = 0;
		for(int i=1; i<=n; i++)
		{
			memset(st, 0, sizeof st);
			if(find(i)) cnt ++ ;
		}
		
		if(cnt < n/2)
		{
			puts("No");
			continue;
		}
		puts("Yes");
		
		memset(st, 0, sizeof st);
		for(int i=1; i<=n; i++)
			if(!st[i])
			{
				st[i] = st[match[i]] = true;
				printf("%d %d\n", i, match[i]);
			}
	}
	
	return 0;
}

詳細信息

Test #1:

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

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
Runtime Error

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:


result: