QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#107509#5423. Perfect MatchingqinsanmaWA 347ms38008kbC++142.2kb2023-05-21 18:39:122023-05-21 18:39:13

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:39:13]
  • 评测
  • 测评结果:WA
  • 用时:347ms
  • 内存:38008kb
  • [2023-05-21 18:39:12]
  • 提交

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

        //  cout<<endl;

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

        }


        //  cout<<endl;

        int flag=0;
        for(int i=1; i<=tot; 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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 10ms
memory: 26884kb

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: 347ms
memory: 38008kb

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)