QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#107502 | #5423. Perfect Matching | qinsanma | TL | 4ms | 50364kb | C++14 | 2.3kb | 2023-05-21 17:36:46 | 2023-05-21 17:36:50 |
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];
set<pair<int,int>>v[1000000+10];
vector<int>ans;
int cnt;
int du[1000000+10];
vector<pair<int,pair<int,int>>>temp;
void dfs(int now)
{
for(auto it:v[now])
{
if(book[it.second])
continue;
book[it.second]=1;
temp.push_back(make_pair(it.first,make_pair(now,it.second)));
dfs(it.first);
cnt++;
ans.push_back(it.second);
temp.push_back(make_pair(now,it));
}
}
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]].insert(make_pair(r[i],i));
v[r[i]].insert(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;
temp.clear();
dfs(l[i]);
if(cnt%2==1)
{
flag=1;
break;
}
for(auto it:temp)
{
v[it.first].erase(it.second);
}
// 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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 50364kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
Yes 4 1 3 6 5 2 Yes 3 1 4 2 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...