Submission #31008

#	Time	Username	Problem	Language	Result	Execution time	Memory
31008		kajebiii	Sorting (IOI15_sorting)	C++14	100 / 100	528 ms	13816 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>

using namespace std;

#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef unsigned long long ull;
typedef pair<double, double> pd;
typedef pair<int, int> pi;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll; typedef pair<ll, pi> plp;
typedef tuple<int, int, int> ti; typedef tuple<ll, int, int> tli;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF * 2;

const int MAX_N = 2e5 + 100;

int N, M, *S, *X, *Y, *P, *Q;
int Now[MAX_N], To[MAX_N], NowR[MAX_N], ToR[MAX_N];
int sortIx;
bool isSort() {
    while(sortIx < N && NowR[sortIx] == ToR[sortIx]) sortIx++;
//    printf("sortIx : %d\n", sortIx);
    return sortIx == N;
}
bool isCan(int m) {
    sortIx = 0;
    for(int i=0; i<N; i++) Now[i] = S[i], To[i] = i;
    for(int i=0; i<N; i++) NowR[Now[i]] = i, ToR[To[i]] = i;
    for(int i=m-1; i>=0; i--) {
        int x = X[i], y = Y[i];
        swap(ToR[To[x]], ToR[To[y]]);
        swap(To[x], To[y]);
    }
    for(int i=0; i<m; i++) P[i] = 0, Q[i] = 0;
    
//    printf("%d start\n", m);
//    printf("N : "); for(int i=0; i<N; i++) printf("%d ", Now[i]); puts("");
//    printf("T : "); for(int i=0; i<N; i++) printf("%d ", To[i]);  puts("");
    if(isSort()) return true;
    for(int i=0; i<m; i++) {
        int x = X[i], y = Y[i];
        swap(ToR[To[x]], ToR[To[y]]);
        swap(To[x], To[y]);
        swap(NowR[Now[x]], NowR[Now[y]]);
        swap(Now[x], Now[y]);

        int l = NowR[sortIx], r = ToR[sortIx];
        swap(NowR[Now[l]], NowR[Now[r]]);
        swap(Now[l], Now[r]);
        P[i] = l; Q[i] = r;
//        printf("N : "); for(int i=0; i<N; i++) printf("%d ", Now[i]); puts("");
//        printf("T : "); for(int i=0; i<N; i++) printf("%d ", To[i]);  puts("");
        if(isSort()) return true;
    }
    return false;
}
int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
    N = n; M = m; S = s; X = x; Y = y; P = p; Q = q;
    int ans = -1;
    for(int l=0, r=M; l<=r; ) {
        int m = (l+r) >> 1;
        if(isCan(m)) ans = m, r = m-1; else l = m+1;
    }
    isCan(ans);
    return ans;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:66:13: warning: declaration of 'int m' shadows a parameter [-Wshadow]
         int m = (l+r) >> 1;
             ^
sorting.cpp:62:39: note: shadowed declaration is here
 int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
                                       ^

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