Submission #795298

#	Time	Username	Problem	Language	Result	Execution time	Memory
795298		jasmin	Sorting (IOI15_sorting)	C++17	0 / 100	10 ms	360 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 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);


    //find swaps
    vector<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.back(); missing.pop_back();
        int b=next[a];

        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: 0 / 8
• Subtask 2: 0 / 12
• Subtask 3: 0 / 16
• Subtask 4: 0 / 18
• Subtask 5: 0 / 20
• Subtask 6: 0 / 26