QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#107512 | #5423. Perfect Matching | qinsanma | WA | 1ms | 26904kb | C++14 | 2.1kb | 2023-05-21 18:43:57 | 2023-05-21 18:43:59 |
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;
map<int,int>mp;
void dfs(int now)
{
book[now]=1;
for(auto it:v[now])
{
if(book[it.first])
continue;
ans.push_back(it.second);
cnt++;
dfs(it.first);
break;
}
}
int main ()
{
int t;
cin>>t;
while(t--)
{
int n;
scanf("%d",&n);
int len=0;
ans.clear();
mp.clear();
int tot=0;
for(int i=1; i<=n; i++)
{
scanf("%lld",&a[i]);
l[i]=a[i]+i;
r[i]=a[i]-i;
if(mp[l[i]])
{
l[i]=mp[l[i]];
}
else
{
tot++;
mp[l[i]]=tot;
l[i]=tot;
}
if(mp[r[i]])
{
r[i]=mp[r[i]];
}
else
{
tot++;
mp[r[i]]=tot;
r[i]=tot;
}
}
for(int i=1; i<=2*n; i++)
{
v[i].clear();
book[i]=0;
}
for(int i=1; i<=n; i++)
{
v[l[i]].push_back(make_pair(r[i],i));
v[r[i]].push_back(make_pair(l[i],i));
}
int flag=0;
for(int i=1; i<=2*n; i++)
{
cnt=0;
if(book[i])
continue;
dfs(i);
if(cnt%2==1)
{
flag=1;
break;
}
}
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: 0
Wrong Answer
time: 1ms
memory: 26904kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
No No No
result:
wrong answer std outputs a valid answer while participant doesn't (test case 1)