Submission #211701

#	Time	Username	Problem	Language	Result	Execution time	Memory
211701		anonymous	Sorting (IOI15_sorting)	C++14	0 / 100	6 ms	640 KiB

sorting

#include "sorting.h"
#include <vector>
#include <iostream>
#define MAXN 200005
using namespace std;
int N, M, goal[MAXN], to[MAXN], P2[MAXN], P[MAXN], eX[MAXN], eY[MAXN];
int at[MAXN], E[MAXN][2]; //which element values to swap
bool vis[MAXN];
int can(int t) {
     int swaps = 0, pt = 0;
     for (int i=0; i<N; i++) {goal[i]=i;}
     for (int i=0; i<t; i++) {swap(goal[eX[i]], goal[eY[i]]);}
     for (int i=0; i<N; i++) {vis[i]=0;}
     for (int i=0; i<N; i++) {to[i]=goal[i];} //end position aim for element with value i
     for (int i=0; i<N; i++) {
        if(vis[i]) {continue;}
        int cur = i;
        swaps--;
        vector<int> Elem;
        while (!vis[cur]) {
            Elem.push_back(P[cur]);
            vis[cur]=true, swaps++;
            cur = to[P[cur]];
        }
        while (Elem.size() > 1) {
            E[pt][0]=Elem[Elem.size()-1];
            E[pt][1]=Elem[Elem.size()-2];
            Elem.pop_back();
            Elem.pop_back();
            Elem.push_back(E[pt][0]);
            pt++;
        }
     }
     return(swaps);
}

int findSwapPairs(int n, int S[], int m, int X[], int Y[], int p[], int q[]) {
    N=n, M=m;
    for (int i=0; i<N; i++) {P[i]=S[i];}
    for (int i=0; i<M; i++) {
        eX[i]=X[i], eY[i]=Y[i];
    }
    int lo = 0, hi = m;
    while (lo + 1 != hi) {
        int mid = (lo + hi) >> 1;
        if (can(mid) <= mid) {hi = mid;}
        else {lo = mid;}
    }
    int ans = hi, swaps = can(hi);
    for (int i=0; i<n; i++) {
        at[S[i]]=i;
        P2[i]=P[i];
    }
    for (int i=0; i<swaps; i++) {
        int e1 = P2[X[i]], e2 = P2[Y[i]];
        swap(P2[X[i]], P2[Y[i]]);
        at[e1] = Y[i], at[e2] = X[i];
        p[i] = at[E[i][0]], q[i] = at[E[i][1]];
        swap(P2[p[i]], P2[q[i]]);
        at[E[i][0]]=q[i], at[E[i][1]]=p[i];
    }
    for (int i=swaps; i<ans; i++) {
        p[i]=q[i]=0;
    }
    return(ans);
}

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