QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#759564#5423. Perfect MatchingwangchunjieWA 251ms21940kbC++141.5kb2024-11-18 10:07:122024-11-18 10:07:19

Judging History

你现在查看的是最新测评结果

  • [2024-11-18 10:07:19]
  • 评测
  • 测评结果:WA
  • 用时:251ms
  • 内存:21940kb
  • [2024-11-18 10:07:12]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N=1e5+5;

int T,n,a[N],dep[N];
map<int,int> x,y;
vector<pair<int,int>> ans,G[N];

int dfs(int u,int pa)
{
    dep[u]=dep[pa]+1;
    vector<int> vec;
    for(auto i:G[u]){
        int v=i.first,id=i.second;
        if(dep[v]){
            if(dep[v]>dep[u])
                vec.emplace_back(id);
            continue;
        }
        int res=dfs(v,u);
        if(res) ans.emplace_back(id,res);
        else vec.emplace_back(id);
    }
    int res=0;
    if(vec.size()&1) res=vec.back(),vec.pop_back();
    for(int i=0;i<vec.size();i+=2)
        ans.emplace_back(vec[i],vec[i+1]);
    return res;
}

void solve()
{
    x.clear(),y.clear(),ans.clear();
    memset(dep,0,sizeof(dep));
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
        x[a[i]+i]=1,y[a[i]-i]=1;
    int cnt=0;
    for(auto &i:x) i.second=++cnt;
    for(auto &i:y) i.second=++cnt;
    for(int i=1;i<=cnt;i++)
        G[i].clear();
    for(int i=1;i<=cnt;i++){
        int u=x[a[i]+i],v=y[a[i]-i];
        G[u].emplace_back(v,i);
        G[v].emplace_back(u,i);
    }
    for(int i=1;i<=cnt;i++){
        if(dep[i]) continue;
        if(dfs(i,0))
            return cout<<"No\n",void();
    }
    cout<<"Yes\n";
    for(auto i:ans)
        cout<<i.first<<' '<<i.second<<'\n';
}

signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--)
        solve();
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 7052kb

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
2 4
1 3
No

result:

ok 3 Cases (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 251ms
memory: 21940kb

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:

No
No
Yes
53 59
62 80
92 110
122 173
194 200
209 254
275 299
317 335
341 353
374 389
407 449
488 533
563 581
590 611
614 629
635 647
737 761
842 878
887 980
1034 1250
1253 1367
1403 1466
1472 1526
1604 1742
1808 1814
1820 1838
1844 1931
1946 2039
2051 2114
2129 2180
2222 2225
2231 2243
2273 2303
240...

result:

wrong answer std outputs a valid answer while participant doesn't (test case 1)