제출 #1193982

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1193982		vivkostov	Sorting (IOI15_sorting)	C++20	0 / 100	1 ms	584 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
int mas[200005],pos[200005],n,a[200005],m,b[200005],c[200005],otg1[200005],otg2[200005];
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++;
        otg1[br]=mas[i];
        otg2[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;
        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[mas[c[i]]]);
        if(i==l&&p0())
        {
            P[i-1]=0;
            Q[i-1]=0;
        }
        else
        {
            swap(pos[otg1[i]],pos[otg2[i]]);
            swap(a[otg1[i]],a[otg2[i]]);
            P[i-1]=pos[otg1[i]]-1;
            Q[i-1]=pos[otg2[i]]-1;
        }
    }
    return l;
}

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