QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#106454#5423. Perfect MatchingcokleTL 3ms6096kbC++111.2kb2023-05-17 20:13:212023-05-17 20:13:22

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:13:22]
  • 评测
  • 测评结果:TL
  • 用时:3ms
  • 内存:6096kb
  • [2023-05-17 20:13:21]
  • 提交

answer

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

using namespace std;

const int N = 1e5 + 10, M = 1e6 + 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=1; i<=n; i++)
	{
		if(i != u && abs(i-u)==abs(a[i]-a[u]))
		{
			if(!st[i])
			{
				st[i] = true;
				if(match[i] == 0 || find(match[i]))
				{
					match[i] = 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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 6096kb

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
Time Limit Exceeded

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: