QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#107510#5423. Perfect MatchingqinsanmaWA 338ms37924kbC++142.1kb2023-05-21 18:41:282023-05-21 18:41:31

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-21 18:41:31]
  • 评测
  • 测评结果:WA
  • 用时:338ms
  • 内存:37924kb
  • [2023-05-21 18:41:28]
  • 提交

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);

    }
}

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: 100
Accepted
time: 4ms
memory: 27040kb

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
Wrong Answer
time: 338ms
memory: 37924kb

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 33
34 79
139 202
244 289
310 316
322 337
382 397
451 460
463 481
517 520
526 556
568 619
661 736
763 790
853 904
934 979
988 1090
1105 1162
1219 1273
1285 1294
1405 1411
1456 1459
1531 1555
1561 1588
1615 1618
1630 1651
1669 1684
1723 1738
1915 1972
2026 2029
2092 2155
2197 2...

result:

wrong answer abs(40-50) != abs(a[40]-a[50]) (test case 1)