Submission #207250

#	Time	Username	Problem	Language	Result	Execution time	Memory
207250		oscarsierra12	Sorting (IOI15_sorting)	C++14	74 / 100	1008 ms	19952 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 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 ;
    for ( int i = 0 ; i <= M ; ++i ) {
        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 ) return i ;
    }
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:43:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if ( swaps.size() % 2 != i % 2 ) swaps.pb ({0,0}) ;
              ~~~~~~~~~~~~~~~~~^~~~~~~~
sorting.cpp:53:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if ( id < swaps.size() ) {
                  ~~~^~~~~~~~~~~~~~
sorting.cpp:69:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if ( swaps.size() <= i ) return i ;
              ~~~~~~~~~~~~~^~~~
sorting.cpp:71:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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