QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#107500#5423. Perfect MatchingqinsanmaTL 4ms26928kbC++142.1kb2023-05-21 17:30:572023-05-21 17:31:01

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:31:01]
  • 评测
  • 测评结果:TL
  • 用时:4ms
  • 内存:26928kb
  • [2023-05-21 17:30:57]
  • 提交

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;
int du[1000000+10];
void dfs(int now)
{


    for(int i=v[now].size()-1;i>=0;i--)
    {
        if(book[v[now][i].second])
            continue;
        book[v[now][i].second]=1;
        ans.push_back(v[now][i].second);
        cnt++;
        dfs(v[now][i].first);
        v[now].pop_back();

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

          if(cnt%2==1)
          {
              flag=1;
              break;
          }


           // cout<<cnt<<endl;

        }

        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: 26928kb

input:

3
6
14 22 33 11 25 36
4
100 10 98 12
4
1 3 5 7

output:

Yes
4 1
2 5
6 3

Yes
3 1
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
100000 99999
99998 99993
99994 99996
99995 99997
99979 99977
99992 99985
99983 99966
99965 99991
99990 99989
99988 99986
99981 99980
99984 99982
99978 99962
99963 99987
99976 99974
99968 99970
99975 99973
99972 99971
99969 99967
99964 99961
99959 99960
99946 99945
99958 99957
99954 99955
99956 9...

result: