Submission #207260

#	Time	Username	Problem	Language	Result	Execution time	Memory
207260		oscarsierra12	Sorting (IOI15_sorting)	C++14	74 / 100	347 ms	15800 KiB

sorting

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

#define ff      first
#define ss      second
#define pb      push_back

using namespace std ;

typedef long long      ll ;
typedef pair<int,int>  ii ;

const int n = 200010 ;

int prv[n], nxt[n] ;
int ind[n], ele[n] ;
int rind[n] ;
int P[n], Q[n] ;
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int p[], int q[]) {
    for ( int i = 0 ; i < N ; ++i )
        rind[S[i]] = i ;
    int lw = 0, hg = M ;
    vector <int> ans ;
    int lst = 0;
    while ( lw < hg ) {
        int i = (lw+hg)/2 ;
        for ( int j = 0 ; j < N ; ++j ) prv[j] = nxt[j] = j ;
        for ( int j = 0 ; j < i ; ++j ) {
            int A = prv[X[j]] ;
            int B = prv[Y[j]] ;
            nxt[A] = Y[j] ;
            prv[Y[j]] = A ;
            nxt[B] = X[j] ;
            prv[X[j]] = B ;
        }
        for ( int j = 0 ; j < N ; ++j ) {
            ele[j] = S[prv[j]] ;
            ind[S[prv[j]]] = j ;
        }
        vector <ii> swaps ;
        for ( int j = 0 ; j < N ; ++j ) {
            if ( ele[j] == j ) continue ;
            swaps.pb ({rind[ele[j]], rind[ele[ind[j]]]}) ;
            ind[ele[j]] = ind[j] ;
            swap (ele[j], ele[ind[j]]) ;
        }
        if ( swaps.size() % 2 != i % 2 ) swaps.pb ({0,0}) ;
        for ( int j = 0 ; j < N ; ++j ) prv[j] = nxt[j] = j ;
        int id = 0 ;
        for ( int j = 0 ; j < i ; ++j ) {
            int A = prv[X[j]] ;
            int B = prv[Y[j]] ;
            nxt[A] = Y[j] ;
            prv[Y[j]] = A ;
            nxt[B] = X[j] ;
            prv[X[j]] = B ;
            if ( id < swaps.size() ) {
                P[j] = nxt[swaps[id].ff] ;
                Q[j] = nxt[swaps[id].ss] ;
            }
            else {
                P[j] = X[j] ;
                Q[j] = Y[j] ;
            }
            A = prv[P[j]] ;
            B = prv[Q[j]] ;
            nxt[A] = Q[j] ;
            prv[Q[j]] = A ;
            nxt[B] = P[j] ;
            prv[P[j]] = B ;
            id++ ;
        }
        if ( swaps.size() <= i ) {
            hg = i ;
            lst = i ;
            for ( int j = 0 ; j < i ; ++j ) p[j] = P[j], q[j] = Q[j] ;
        }
        else lw = i+1 ;
    }
    return lst ;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:47:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if ( swaps.size() % 2 != i % 2 ) swaps.pb ({0,0}) ;
              ~~~~~~~~~~~~~~~~~^~~~~~~~
sorting.cpp:57:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if ( id < swaps.size() ) {
                  ~~~^~~~~~~~~~~~~~
sorting.cpp:73:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if ( swaps.size() <= i ) {
              ~~~~~~~~~~~~~^~~~

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