QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#107512#5423. Perfect MatchingqinsanmaWA 1ms26904kbC++142.1kb2023-05-21 18:43:572023-05-21 18:43:59

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:43:59]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:26904kb
  • [2023-05-21 18:43: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;
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);
        break;

    }
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 26904kb

input:

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

output:

No
No
No

result:

wrong answer std outputs a valid answer while participant doesn't (test case 1)