Submission #207677

#	Time	Username	Problem	Language	Result	Execution time	Memory
207677		DodgeBallMan	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	90 ms	28488 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
#define pii pair<int, int>
#define x first
#define y second 

using namespace std;

const int N = 1e5 + 10;
vector<pii> coord;
vector<int> l[N], r[N], s;
int n, arr[N];
long long ans, fen[N];

long long query( int x ) {
    long long ret = 0;
    for( int i = x ; i > 0 ; i -= i & -i ) ret += fen[i];
    return ret;
}

void up( int x ) {
    for( int i = x ; i < N ; i += i & -i ) fen[i] += 1;
}

long long count_swaps( vector<int> S ) {
    n = S.size() / 2, s = S;
    for( int i = 0 ; i < n * 2 ; i++ ) {
        if( s[i] < 0 ) l[abs( s[i] )].emplace_back( i + 1 );
        else r[ abs( s[i] )].emplace_back( i + 1 );
    }
    for( int i = 1 ; i <= 100000 ; i++ ) 
        sort( l[i].begin(), l[i].end(), greater<int>() ), sort( r[i].begin(), r[i].end(), greater<int>() );
    for( int i = 1 ; i <= 100000 ; i++ ) {
        for( int j = 0 ; j < l[i].size() ; j++ ) {
            //printf("%d %d\n",r[i][j],l[i][j]);
            coord.emplace_back( pii( r[i][j], l[i][j] ) );
        }
    }
    sort( coord.begin(), coord.end(), greater<pii>() );
    for( int i = 0 ; i < coord.size() ; i++ ) {
        int now = n - i - 1;
        arr[2*now] = coord[i].y, arr[2*now+1] = coord[i].x;
    }
    //for( int i = 0 ; i < 2*n ; i++ ) printf("%d ",arr[i]);
    //printf("\n");
    for( int i = 2*n - 1 ; i >= 0 ; i-- ) {
        //cout << query( arr[i] ) << endl;
        ans += query( arr[i] ), up( arr[i] );
    }
    return ans;
}

/*int main()
{
    int ne;
    vector<int> vec;
    scanf("%d",&ne);
    for( int i = 0, a ; i < ne ; i++ ) {
        scanf("%d",&a);
        vec.emplace_back( a );
    }
    printf("%lld",count_swaps( vec ) );
}*/

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:34:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for( int j = 0 ; j < l[i].size() ; j++ ) {
                          ~~^~~~~~~~~~~~~
shoes.cpp:40:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for( int i = 0 ; i < coord.size() ; i++ ) {
                      ~~^~~~~~~~~~~~~~

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