Submission #31823

#	Time	Username	Problem	Language	Result	Execution time	Memory
31823		top34051	Sorting (IOI15_sorting)	C++14	100 / 100	223 ms	13916 KiB

sorting

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

int n, s[maxn];
int a[maxn], pos[maxn];
pair<int,int> sw[maxn];

int get(int rec) {
    int i,x,cnt;
    for(i=0;i<n;i++) a[i] = s[i];
    for(i=0;i<n;i++) pos[a[i]] = i;
    cnt = 0;
    for(i=0;i<n;i++) {
        x = pos[i];
        if(i!=x) {
            pos[a[i]] = x;
            swap(a[i], a[x]);
            if(rec) sw[cnt] = {a[i],a[x]};
            cnt++;
        }
    }
    return cnt;
}

bool check(int x,int S[],int X[],int Y[]) {
    int i;
    for(i=0;i<n;i++) s[i] = S[i];
    for(i=0;i<=x;i++) swap(s[X[i]], s[Y[i]]);
    if(get(0)<=x+1) return 1;
    else return 0;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    int i,x,now,l,r,mid;
    n = N;
    for(i=0;i<n;i++) s[i] = S[i];
    l = -1; r = N;
    while(l<=r) {
        mid = (l+r)/2;
        if(check(mid,S,X,Y)) now = mid, r = mid-1;
        else l = mid+1;
    }
    check(now,S,X,Y);
    get(1);
    for(i=0;i<n;i++) s[i] = S[i];
    for(i=0;i<n;i++) pos[s[i]] = i;
    for(i=0;i<now+1;i++) {
        swap(pos[s[X[i]]], pos[s[Y[i]]]);
        swap(s[X[i]], s[Y[i]]);
        P[i] = pos[sw[i].first];
        Q[i] = pos[sw[i].second];
        swap(pos[s[P[i]]], pos[s[Q[i]]]);
        swap(s[P[i]], s[Q[i]]);
    }
    return now+1;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:36:11: warning: unused variable 'x' [-Wunused-variable]
     int i,x,now,l,r,mid;
           ^
sorting.cpp:35:39: warning: unused parameter 'M' [-Wunused-parameter]
 int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
                                       ^
sorting.cpp:36:13: warning: 'now' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int i,x,now,l,r,mid;
             ^~~

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