QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#107498#5423. Perfect MatchingqinsanmaTL 4ms27096kbC++142.0kb2023-05-21 17:23:182023-05-21 17:23:21

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 17:23:21]
  • 评测
  • 测评结果:TL
  • 用时:4ms
  • 内存:27096kb
  • [2023-05-21 17:23:18]
  • 提交

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;

void dfs(int now)
{


    for(auto it:v[now])
    {
        if(book[it.second])
            continue;
        book[it.second]=1;
        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();
        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]);

           // cout<<cnt<<endl;
            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: 4ms
memory: 27096kb

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
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
1 14
15 16
20 21
22 2
3 34
32 39
38 4
5 7
25 23
6 8
9 10
11 12
24 30
29 13
17 18
19 26
27 28
35 36
37 44
46 42
41 48
49 43
45 47
51 50
33 40
53 54
56 57
58 62
63 64
65 66
67 69
68 70
71 73
72 52
55 59
60 61
84 83
74 75
76 78
77 80
81 82
87 88
86 94
93 85
89 91
90 95
96 107
109 92
98 99
104 106
9...

result: