제출 #1192782

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1192782		simona1230	정렬하기 (IOI15_sorting)	C++20	20 / 100	1 ms	328 KiB

sorting

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

//static FILE *_inputFile, *_outputFile;

int n;
vector<pair<int,int> > v;
int p[200001],pos[200001];
void swaps()
{
    for(int i=0; i<n; i++)
        pos[p[i]]=i;
    for(int i=0; i<n; i++)
    {
        if(p[i]!=i)
        {
            v.push_back({i,p[i]});
            pos[p[i]]=pos[i];
            swap(p[i],p[pos[i]]);
        }
    }
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[],int P[],int Q[])
{
    n=N;
    int ans=0;
    int l=0,r=M;
    while(l<=r)
    {
        int m=(l+r)/2;
        for(int i=0; i<n; i++)
            p[i]=S[i];
        for(int i=0; i<m; i++)
            swap(p[X[i]],p[Y[i]]);
        v.clear();
        swaps();
        if(v.size()<=m)
        {
            r=m-1;
            ans=m;
        }
        else l=m+1;
    }

    for(int i=0; i<n; i++)
        p[i]=S[i];
    for(int i=0; i<ans; i++)
        swap(p[X[i]],p[Y[i]]);
    v.clear();
    swaps();
    //for(int i=0;i<ans;i++)
    //    fprintf(_outputFile, "%d %d ", v[i].first, v[i].second);

    for(int i=0;i<n;i++)
        p[i]=S[i];
    for(int i=0; i<n; i++)
        pos[p[i]]=i;

    for(int i=0; i<ans; i++)
    {
        pos[p[Y[i]]]=X[i];
        pos[p[X[i]]]=Y[i];
        swap(p[X[i]],p[Y[i]]);

        P[i]=pos[v[i].first];
        Q[i]=pos[v[i].second];
        pos[p[P[i]]]=Q[i];
        pos[p[Q[i]]]=P[i];
        swap(p[P[i]],p[Q[i]]);
    }
    return ans;
}

/*
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>p[i];
}
*/

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