Submission #1190352

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190352		simona1230	Sorting (IOI15_sorting)	C++20	16 / 100	0 ms	328 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;

//static FILE *_inputFile, *_outputFile;

int num;
int s[200001],pos[200001];
int p[200001],q[200001];

void change(int i,int j)
{
    pos[s[i]]=j;
    pos[s[j]]=i;
    swap(s[i],s[j]);
}

void change1(int i,int j)
{
    p[num]=i;
    q[num]=j;

    pos[s[i]]=j;
    pos[s[j]]=i;

    swap(s[i],s[j]);
    num++;
    change(0,1);
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[],int P[],int Q[])
{
    for(int i=0;i<N;i++)
        pos[S[i]]=i,s[i]=S[i];
    bool f=0;
    for(int i=0;i<N;i++)
        if(s[i]!=i)f=1;
    if(!f)return 0;

    change(0,1);
    f=0;
    for(int i=0;i<N;i++)
        if(s[i]!=i)f=1;
    if(!f)return 1;

    if(pos[0]>1)
        change1(0,pos[0]);

    if(pos[1]>1)
    {
        if(pos[0]==0)change1(1,pos[1]);
        else change1(0,pos[1]);
    }

    for(int i=2;i<N;i++)
    {
        if(s[i]!=i)
            change1(i,pos[i]);
    }
    if(pos[0]==0)num++;
    for(int i=0;i<num;i++)
        P[i]=p[i],Q[i]=q[i];
    return num;
}

/*int n,a[200001],x[200001],y[200001];
int pp[200001],qq[200001];
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
        for(int i=0;i<=100;i++)
            x[i]=0,y[i]=1;
    int ans=findSwapPairs(n,a,100,x,y,pp,qq);
    for(int i=0;i<ans;i++)
    {
        swap(a[0],a[1]);
        swap(a[p[i]],a[q[i]]);
        cout<<p[i]<<" "<<q[i]<<endl;
    }

    for(int i=0;i<n;i++)
        cout<<a[i]<<" ";
    cout<<endl;
    cout<<ans<<endl;
}*/

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