Submission #282917

#	Time	Username	Problem	Language	Result	Execution time	Memory
282917		Badrangiikh	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	352 ms	275064 KiB

shoes

    #include<bits/stdc++.h>
    #include "shoes.h"
    using namespace std;

    int n , pos , indx , m , x , y , z ;
    stack < int > r [ 200005 ] ;
    stack < int > l [ 200005 ] ;
    int a [ 200005 ] ;
    int bit [ 200005 ] ;
    bool vis [ 200005 ] ;

    void add ( int indx ) {
        while ( indx <= n ) {
            bit [ indx ] ++ ;
            indx += indx & ( -indx ) ;
        }
    }

    int get ( int indx ) {
        int sum = 0 ;
        while ( indx > 0 ) {
            sum += bit [ indx ] ;
            indx -= indx & ( -indx ) ;
        }
        return sum ;
    }

    int move ( int indx , int pos ) {
        vis [ indx ] = 1 ;
        add ( indx ) ;
        return ( pos - ( indx - get ( indx - 1 ) ) ) ;
    }

    long long count_swaps( vector<int> arr ) {
        n = arr . size ( ) ;
        for ( int i = 1 ; i <= n ; i ++ ) {
            a [ i ] = arr [ i - 1 ] ;
        }
        for ( int i = 1 ; i <= n ; i ++ ) {
            if ( a [ i ] < 0 ) {
                l [ -a [ i ] ] . push ( i ) ;
            }
            else {
                r [ a [ i ] ] . push ( i ) ;
            }
        }
        long long ans = 0 ;
        x = n ;
        for ( int i = n ; i >= 1 ; i -- ) {
            if ( vis [ i ] == 0 ) {
                y = abs ( a [ i ] ) ;
                ans += move ( r [ y ] . top ( ) , x ) ;
                ans += move ( l [ y ] . top ( ) , x - 1 ) ;
                r [ y ] . pop ( ) ;
                l [ y ] . pop ( ) ;
                x -= 2 ;
            }
        } 
        return ans ;
    }

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15