QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#107499 | #5423. Perfect Matching | qinsanma | TL | 1ms | 26980kb | C++14 | 2.2kb | 2023-05-21 17:27:20 | 2023-05-21 17:27:24 |
Judging History
answer
# include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll b[1000000+10],lisan[1000000+10],l[1000000+10],r[1000000+10],a[1000000+10];
int book[1000000+10];
vector<pair<int,int>>v[1000000+10];
vector<int>ans;
int cnt;
void dfs(int now)
{
for(auto it:v[now])
{
if(book[it.second])
continue;
book[it.second]=1;
ans.push_back(it.second);
cnt++;
dfs(it.first);
}
}
int main ()
{
int t;
cin>>t;
while(t--)
{
int n;
scanf("%d",&n);
int len=0;
ans.clear();
for(int i=1; i<=n; i++)
{
scanf("%lld",&a[i]);
len++;
lisan[len]=a[i]+i;
len++;
lisan[len]=a[i]-i;
l[i]=a[i]+i;
r[i]=a[i]-i;
}
sort(lisan+1,lisan+1+2*n);
len=unique(lisan+1,lisan+1+2*n)-lisan-1;
for(int i=1; i<=len; i++)
{
v[i].clear();
book[i]=0;
}
// cout<<endl;
for(int i=1; i<=n; i++)
{
l[i]=lower_bound(lisan+1,lisan+1+len,l[i])-lisan;
r[i]=lower_bound(lisan+1,lisan+1+len,r[i])-lisan;
v[l[i]].push_back(make_pair(r[i],i));
v[r[i]].push_back(make_pair(l[i],i));
// cout<<l[i]<<" "<<r[i]<<endl;
}
// cout<<endl;
int flag=0;
for(int i=1; i<=n; i++)
{
cnt=0;
for(auto it:v[r[i]])
{
if(book[it.second])
continue;
cnt=0;
dfs(it.first);
if(cnt%2==1)
{
flag=1;
break;
}
}
// cout<<cnt<<endl;
}
if(flag)
{
cout<<"No"<<'\n';
}
else
{
cout<<"Yes"<<'\n';
for(int i=0;i<ans.size();i++)
{
cout<<ans[i]<<" "<<ans[i+1]<<'\n';
i++;
}
cout<<'\n';
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 26980kb
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:
Yes 1 14 15 16 20 21 22 2 3 34 32 39 38 4 5 7 25 23 6 8 9 10 11 12 24 30 29 13 17 18 19 26 27 28 35 36 37 44 46 42 41 48 49 43 45 47 51 50 33 40 53 54 56 57 58 62 63 64 65 66 67 69 68 70 71 73 72 52 55 59 60 61 84 83 74 75 76 78 77 80 81 82 87 88 86 94 93 85 89 91 90 95 96 107 109 92 98 99 104 106 9...