Submission #1255347

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255347		lambd47	Sorting (IOI15_sorting)	C++20	100 / 100	200 ms	15336 KiB

sorting

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

int n;

int dist(vector<int> a, vector<int> b){
    vector<int> marc(a.size(),0);
    vector<int> rb(b.size());
    for(int i=0;i<n;i++){
        rb[b[i]]=i;
    }
    int d=n;
    for(int i=0;i<n;i++){
        int at=a[i];
        if(marc[at])continue;
        d--;
        while(!marc[at]){
            marc[at]=1;
            at=a[rb[at]];
        }
    }
    return d;
}


int findSwapPairs(int N, int s[], int M, int x[], int y[], int P[], int Q[]){
    n=N;
    vector<int> ord(n);
    vector<int> vec(n);
    for(int i=0;i<n;i++)vec[i]=s[i];

    int l=0;int r=n+1;
    while(l<=r){
        int m=(l+r)/2;
        iota(ord.begin(),ord.end(),0);
        for(int i=m-1;i>=0;i--){
            swap(ord[x[i]],ord[y[i]]);
        }
        int d=dist(vec,ord);
        if(d<=m){
            r=m-1;
        }
        else{
            l=m+1;
        }
    }
    int rp=r+1;
    

    iota(ord.begin(),ord.end(),0);
    for(int i=rp-1;i>=0;i--){
        swap(ord[x[i]],ord[y[i]]);
    }
    vector<int> marc(n,0);

    vector<pair<int,int>> trocas;
    vector<int> rv(n);
    for(int i=0;i<n;i++){
        rv[vec[i]]=i;
    }

    for(int i=0;i<n;i++){
        if(marc[ord[i]])continue;
        int at=ord[i];
        marc[at]=1;
        int vai=ord[rv[at]];
        if(at==vai)continue;
        while(vai!=ord[i]){
            marc[vai]=1;
            trocas.push_back({at,vai});
            at=vai;
            vai=ord[rv[vai]];
        }
    }

    vector<int> at(n);
    vector<int> onde(n);
    vector<pair<int,int>> resp;
    at=vec;
    for(int i=0;i<n;i++){
        onde[at[i]]=i;
    }
    for(int i=0;i<trocas.size();i++){
        swap(at[x[i]],at[y[i]]);
        swap(onde[at[x[i]]],onde[at[y[i]]]);
        resp.push_back({onde[trocas[i].first],onde[trocas[i].second]});
    }
    while(resp.size()!=rp){
        resp.push_back({0,0});
    }
    for(int i=0;i<rp;i++){
        P[i]=resp[i].first;
        Q[i]=resp[i].second;
    }
    return rp;



}

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