Submission #1219344

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219344		AlperenT_	Sorting (IOI15_sorting)	C++20	100 / 100	168 ms	19540 KiB

sorting

#include "sorting.h"

#include <bits/stdc++.h> 


#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define pii pair<int,int> 
#define all(a) a.begin(),a.end()
#define S second 
#define sz(a) (int)a.size()
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define ld long double
#define ll long long
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn =  6e5 + 100 , inf = 1e9+ 10 , mod = 1e9 + 7 ; 
int b[maxn] , n , a[maxn] , o[maxn] , c[maxn], B[maxn]  , ID[maxn] , P[maxn] , Q[maxn] , x[maxn] , y[maxn] , S[maxn];

int sl(int z){
    rep(i , 0 ,n-1){
        a[i] = S[i] ;
        b[i] = S[i] ;
        ID[a[i]] = i ;
    }
    rep(i ,0 ,z){
        swap(b[x[i]] , b[y[i]]) ;
    }
    vector <pii> vec ;
    rep(i , 0, n-1){
        while(b[i] != i){
            vec.pb({b[i] , b[b[i]]}) ;
            swap(b[i] , b[b[i]]) ;
        }
    }
    if(sz(vec) > z+1) return 0 ;
    rep(i , 0 ,z){
        swap(a[x[i]] , a[y[i]]);
        swap(ID[a[x[i]]] , ID[a[y[i]]]);
        if(i < sz(vec)){
            P[i] = ID[vec[i].F] ;
            Q[i] = ID[vec[i].S] ;
        } else{
            P[i] = Q[i] = 0;
        }
        swap(a[P[i]] , a[Q[i]]) ;
        swap(ID[a[P[i]]],  ID[a[Q[i]]]) ;
    }
    return 1; 
}

int findSwapPairs(int N, int SS[], int m, int X[], int Y[], int p[], int q[]){
    n = N ; 
    rep(i , 0 , m-1){
        x[i] = X[i] ;
        y[i] = Y[i] ;
    }
    rep(i , 0 ,n-1){
        S[i] = SS[i] ;
    }
    int l = -1 , r = n;
    while(r-l > 1){
         int mid = (l+r)/2  ;
         if(sl(mid-1) == 1){
             r = mid ;
         }else{
             l = mid ;
         }
     }   
     sl(r-1) ;
    rep(i , 0 ,r-1){
        p[i] = P[i] ;
        q[i]= Q[i]; 
    }
    return r ;
}

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