QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#107500 | #5423. Perfect Matching | qinsanma | TL | 4ms | 26928kb | C++14 | 2.1kb | 2023-05-21 17:30:57 | 2023-05-21 17:31:01 |
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;
int du[1000000+10];
void dfs(int now)
{
for(int i=v[now].size()-1;i>=0;i--)
{
if(book[v[now][i].second])
continue;
book[v[now][i].second]=1;
ans.push_back(v[now][i].second);
cnt++;
dfs(v[now][i].first);
v[now].pop_back();
}
}
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;
dfs(l[i]);
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 26928kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
Yes 4 1 2 5 6 3 Yes 3 1 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 100000 99999 99998 99993 99994 99996 99995 99997 99979 99977 99992 99985 99983 99966 99965 99991 99990 99989 99988 99986 99981 99980 99984 99982 99978 99962 99963 99987 99976 99974 99968 99970 99975 99973 99972 99971 99969 99967 99964 99961 99959 99960 99946 99945 99958 99957 99954 99955 99956 9...