Submission #207689

#	Time	Username	Problem	Language	Result	Execution time	Memory
207689		DodgeBallMan	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	95 ms	26824 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];
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;
    //cout << n << endl;
    for( int i = 0 ; i < n * 2 ; i++ ) {
        //printf("%d ",s[i]);
        if( s[i] < 0 ) l[abs( s[i] )].emplace_back( i + 1 );
        else r[ abs( s[i] )].emplace_back( i + 1 );
    }
    //cout << "hell0";
    for( int i = 0 ; i < N ; i++ ) {
        //printf("%d ",i);
        sort( l[i].begin(), l[i].end(), greater<int>() ), sort( r[i].begin(), r[i].end(), greater<int>() );
    }
    for( int i = 0 ; i < N ; i++ ) {
        //printf("i%d ",i);
        //printf("%d\n",l[i].size());
        for( int j = 0 ; j < ( int )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++ ) {
        //cout << coord[i].x << " " << coord[i].y << endl;
        int now = n - i;
        arr[coord[i].y] = (2*now)-1 , arr[coord[i].x] = 2*now;
    }
    //for( int i = 1 ; i <= 2*n ; i++ ) printf("%d ",arr[i]);
    //printf("\n");
    for( int i = 2*n ; 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:47: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