QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#107502#5423. Perfect MatchingqinsanmaTL 4ms50364kbC++142.3kb2023-05-21 17:36:462023-05-21 17:36:50

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

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];
set<pair<int,int>>v[1000000+10];
vector<int>ans;
int cnt;
int du[1000000+10];
vector<pair<int,pair<int,int>>>temp;
void dfs(int now)
{
   for(auto it:v[now])
   {

       if(book[it.second])
        continue;
       book[it.second]=1;
       temp.push_back(make_pair(it.first,make_pair(now,it.second)));
       dfs(it.first);
       cnt++;
       ans.push_back(it.second);
       temp.push_back(make_pair(now,it));


   }
}
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]].insert(make_pair(r[i],i));
            v[r[i]].insert(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;

            temp.clear();
          dfs(l[i]);

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


          for(auto it:temp)

          {
              v[it.first].erase(it.second);
          }
           // 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: 50364kb

input:

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

output:

Yes
4 1
3 6
5 2

Yes
3 1
4 2

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:


result: