Submission #1245095

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245095		caacrugon	Sorting (IOI15_sorting)	C++20	20 / 100	2 ms	580 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long

ll n;
vector<ll> ln;
vector<pair<ll,ll>> em;

bool possi(ll m){
    vector<ll> a=ln;
    ll limit=m;
    for(ll i=0;i<limit;i++) swap(a[em[i].first],a[em[i].second]);
    int N=n;
    vector<pair<ll,int>> temp;
    for(int i=0;i<N;i++) temp.push_back({a[i],i});
    sort(temp.begin(),temp.end());
    vector<int> p(N);
    for(int i=0;i<N;i++) p[temp[i].second]=i;
    vector<bool> vis(N,false);
    ll cycles=0;
    for(int i=0;i<N;i++) if(!vis[i]){
        int j=i;
        while(!vis[j]){
            vis[j]=true;
            j=p[j];
        }
        cycles++;
    }
    ll min_swaps=N-cycles;
    return min_swaps<=m;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    ln.resize(N);
    n=N;
    em.resize(M);
    for(int i=0;i<N;i++){
        ln[i]=S[i];
    }
    for(int i=0;i<M;i++){
        em[i].first=X[i];
        em[i].second=Y[i];
    }
    ll l=0,r=M,ans=M;
    while(l<=r){
        ll m=l+((r-l)/2);
        if(possi(m)){
            ans=m;
            r=m-1;
        }else{
            l=m+1;
        }
    }
    vector<ll> a=ln;
    ll limit=ans;
    for(ll i=0;i<limit;i++) swap(a[em[i].first],a[em[i].second]);
    vector<pair<ll,int>> temp;
    for(int i=0;i<N;i++) temp.push_back({a[i],i});
    sort(temp.begin(),temp.end());
    vector<int> p(N);
    for(int i=0;i<N;i++) p[temp[i].second]=i;
    vector<bool> vis(N,false);
    ll R=0;
    for(int i=0;i<N;i++){ 
      if(!vis[i] && p[i]!=i){
        int cur=i;
        vector<int> ciclo;
        while(!vis[cur]){
            ciclo.push_back(cur);
            vis[cur]=true;
            cur=p[cur];
        }
        for(int j=1;j<ciclo.size();j++){
            P[R]=ciclo[0];
            Q[R]=ciclo[j];
            R++;
        }
      }
    }
    return ans;
}

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