Submission #1219323

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219323		LeonidCuk	Sorting (IOI15_sorting)	C++20	100 / 100	93 ms	13020 KiB

sorting

#include <bits/stdc++.h>
//#include "sorting.h"
using namespace std;
int vrni(vector<int>v,vector<pair<int,int>>&g,int m)
{
    int n=v.size(),sum=0;
    for(int i=0;i<m;i++)
    {
        swap(v[g[i].first],v[g[i].second]);
    }
    vector<bool>vis(n);
    for(int i=0;i<n;i++)
    {
        if(vis[i])continue;
        sum++;
        int a=i;
        vis[i]=true;
        while(v[a]!=i)
        {
            vis[v[a]]=true;
            a=v[a];
        }
    }
    return n-sum;
}
int findSwapPairs(int n, int S[], int m, int X[], int Y[], int P[], int Q[])
{
    int l=0,r=n;
    vector<pair<int,int>>g,res1;
    vector<int>v,v2(n);
    for(int i=0;i<n;i++)
    {
        v2[S[i]]=i;
        v.push_back(S[i]);
        g.push_back({X[i],Y[i]});
    }
    while(l<r)
    {
        int m=(l+r)/2,a=vrni(v,g,m);
        if(a<=m)r=m;
        else l=m+1;
    }
    vector<int>v1=v;
    for(int i=0;i<l;i++)
    {
        swap(v1[g[i].first],v1[g[i].second]);
    }
    vector<bool>vis(n);
    for(int i=0;i<n;i++)
    {
        if(vis[i])continue;
        int a=i;
        vis[i]=true;
        while(v1[a]!=i)
        {
            vis[v1[a]]=true;
            res1.push_back({a,v1[a]});
            a=v1[a];
        }
    }
    for(int i=0;i<l;i++)
    {
        int a=g[i].first,b=g[i].second;
        swap(v2[v[a]],v2[v[b]]);
        swap(v[a],v[b]);
        P[i]=v2[res1[i].first];
        Q[i]=v2[res1[i].second];
        a=P[i];b=Q[i];
        swap(v2[v[a]],v2[v[b]]);
        swap(v[a],v[b]);
    }
    return l;
}

• Subtask 1: 8 / 8
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 20 / 20
• Subtask 6: 26 / 26