Submission #1194019

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194019		vivkostov	Sorting (IOI15_sorting)	C++20	100 / 100	102 ms	20840 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
int mas[600005],pos[600005],n,a[600005],m,b[600005],c[600005],sot1[600005],sot2[600005],otg1[600005],otg2[600005];
bool check(int p)
{
    for(int i=1;i<=n;i++)
    {
        mas[i]=a[i];
        pos[mas[i]]=i;
    }
    for(int i=1;i<=p;i++)
    {
        swap(mas[b[i]],mas[c[i]]);
        swap(pos[mas[b[i]]],pos[mas[c[i]]]);
    }
    int br=0;
    for(int i=1;i<=n;i++)
    {
        if(mas[i]==i)continue;
        br++;
        sot1[br]=mas[i];
        sot2[br]=i;
        swap(pos[mas[i]],pos[i]);
        swap(mas[pos[mas[i]]],mas[i]);
    }
    if(br<=p)return true;
    return false;
}
bool p0()
{
    int br=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]==i)br++;
    }
    if(br==n)return true;
    return false;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
{
    n=N;
    m=M;
    for(int i=1;i<=n;i++)
    {
        a[i]=S[i-1]+1;
    }
    for(int i=1;i<=m;i++)
    {
        b[i]=X[i-1]+1;
        c[i]=Y[i-1]+1;
    }
    if(p0())return 0;
    int l=1,r=m,mid;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(check(mid))
        {
            r=mid-1;
            for(int i=1;i<=mid;i++)
            {
                otg1[i]=sot1[i];
                otg2[i]=sot2[i];
            }
        }
        else l=mid+1;
    }
    for(int i=1;i<=n;i++)pos[a[i]]=i;
    for(int i=1;i<=l;i++)
    {
        swap(a[b[i]],a[c[i]]);
        swap(pos[a[b[i]]],pos[a[c[i]]]);
        if(i==l&&p0())
        {
            P[i-1]=0;
            Q[i-1]=0;
        }
        else
        {
            swap(pos[otg1[i]],pos[otg2[i]]);
            swap(a[pos[otg1[i]]],a[pos[otg2[i]]]);
            P[i-1]=pos[otg1[i]]-1;
            Q[i-1]=pos[otg2[i]]-1;
        }
    }
    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