Submission #795707

#	Time	Username	Problem	Language	Result	Execution time	Memory
795707		jasmin	Sorting (IOI15_sorting)	C++17	100 / 100	128 ms	19624 KiB

sorting

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

int cnt_cycle(vector<int>& s, int n){

    vector<bool> vis(n, false);
    int cnt=0;
    for(int v=0; v<n; v++){
        if(vis[v]) continue;
        
        cnt++;

        int mom=s[v];
        while(!vis[mom]){

            vis[mom]=true;
            mom=s[mom];
        }
    }

    return cnt;
}

int cnt_cycles(int rounds, vector<int> s, int x[], int y[], int n){
    for(int i=0; i<rounds; i++){
        swap(s[x[i]], s[y[i]]);
    }

    int cnt=0;
    vector<bool> vis(n);
    for(int v=0; v<n; v++){
        if(!vis[v]) cnt++;

        while(!vis[v]){
            vis[v]=true;

            v=s[v];
        }
    }
    return cnt;
}

int findSwapPairs(int n, int S[], int m, int x[], int y[], int p[], int q[]) {
    
    //initialize
    vector<int> s(n);
    for(int i=0; i<n; i++){
        s[i] = S[i];
    }

    //cnt minimal rounds
    /*int rounds=-1;
    int cnt = n-cnt_cycle(s, n);
    for(int i=0; i<m; i++){

        if(cnt<=i){
            rounds = i;
            break;
        }

        swap(s[x[i]], s[y[i]]);
        cnt = n-cnt_cycle(s, n);
    }

    if(rounds==-1 && cnt<=m){
        rounds=m;
    }
    assert(rounds!=-1);*/

    int l=0; int r=m;
    int ans=m;
    while(l<=r){
        int mi=l+(r-l)/2;

        if(n-cnt_cycles(mi, s, x, y, n) <= mi){
            ans=mi;
            r=mi-1;
        }
        else{
            l=mi+1;
        }
    }
    int rounds=ans;

    for(int i=0; i<rounds; i++){
        swap(s[x[i]], s[y[i]]);
    }

    //find swaps
    deque<int> missing;
    vector<int> next(n);

    vector<bool> vis(n, false);
    for(int v=0; v<n; v++){
        if(vis[v]) continue;

        int mom = v;
        while(!vis[mom]){
            vis[mom]=true;

            missing.push_back(s[mom]);
            next[s[mom]] = s[s[mom]];

            mom=s[mom];
        }
        missing.pop_back(); //last in cycle doesn't need to be swapped anymore
    }

    vector<int> pos(n);
    for(int i=0; i<n; i++){
        pos[s[i]]=i;
    }

    for(int i=rounds-1; i>=0; i--){

        if(missing.empty()){

            p[i]=q[i]=0;
            continue;
        }

        int a=missing.front(); missing.pop_front();
        int b=next[a];

        //cout << a << " " << b << ": " << pos[a] << " " << pos[b] << "\n";

        p[i] = pos[a];
        q[i] = pos[b];

        swap(pos[s[x[i]]], pos[s[y[i]]]);
        swap(s[x[i]], s[y[i]]);
    }

    return rounds;
}

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