Submission #1216517

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216517		mircea_007	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	43 ms	15392 KiB

shoes

#include "shoes.h"

#include <assert.h>

#include <vector>
#include <numeric>
#include <algorithm>

#include <iostream>

namespace __Sol__ {
  using ll = long long;
  template<class T> using vec = std::vector<T>;

  struct AIB {
    vec<int> aib;
    AIB( int n ): aib(n + 1, 0) {}
    int query( int idx ) {
      int ret = 0;
      for( int i = idx; i; i &= (i - 1) )
        ret += aib[i];
      return ret;
    }

    void update( int idx, int delta ) {
      for( int i = idx + 1; i < (int)aib.size(); i += (i & -i) )
        aib[i] += delta;
    }
  };

  ll count_swaps( const vec<int> &s ) {
    int n = (int)s.size() / 2;

    vec<vec<int>> left(n + 1);
    vec<vec<int>> right(n + 1);
    for( int i = 0; i < 2 * n; i++ )
      if( s[i] < 0 )
        left[-s[i]].push_back( i );
      else
        right[+s[i]].push_back( i );

    vec<std::pair<int, int>> pairs;
    for( int x = 1; x <= n; x++ )
      for( int i = 0; i < (int)left[x].size(); i++ )
        pairs.emplace_back( left[x][i], right[x][i] );

    ll ret = 0;
    vec<int> pair(2 * n);
    for( auto [a, b]: pairs ){
      pair[a] = b;
      pair[b] = a;
      ret += (a > b);
    }

    AIB aib(2 * n);
    for( int i = 0; i < 2 * n; i++ )
      aib.update( i, +1 );
    for( int i = 0; i < 2 * n; i++ ){
      if( pair[i] < i ) continue;
      int j = pair[i];
      ret += aib.query( j ) - aib.query( i + 1 );
      aib.update( j, -1 );
    }

    return ret;
  }
}

long long count_swaps(std::vector<int> s) { return __Sol__::count_swaps(s); }

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