QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#106453 | #5423. Perfect Matching | cokle | RE | 1ms | 8160kb | C++11 | 1.2kb | 2023-05-17 20:08:42 | 2023-05-17 20:08:47 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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...