Submission #651430

#	Time	Username	Problem	Language	Result	Execution time	Memory
651430		pauloamed	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	284 ms	27468 KiB

shoes

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

#define ll long long

struct BIT{
  int n; vector<ll> v;
  BIT(int m = 0):n(m + 2), v(vector<ll>(n)){}

  int query(int i){ ll ans = 0;
    for(i+=2; i > 0; i -= i & (-i))
      ans += v[i];
    return ans;
  }

  void update(int i, ll val){
    for(i+=2; i < n; i += i & (-i)) 
      v[i] += val;
  }
};

ll count_swaps(vector<int> v){
  int n = v.size();



  map<int, vector<int>> id2pos[2];
  for(int i = 0; i < n; ++i){
    if(v[i] < 0) id2pos[1][-v[i]].push_back(i);
    else id2pos[0][v[i]].push_back(i);
  }

  vector<pair<int,int>> u;
  for(auto [x, _] : id2pos[0]){
    for(int i = 0; i < id2pos[0][x].size(); ++i){
      int a = id2pos[0][x][i];
      int b = id2pos[1][x][i];
      u.push_back({min(a, b), max(a, b)});
    }
  }
  sort(u.begin(), u.end());

  BIT bit(n);

  ll ans = 0;
  for(auto [l, r] : u){
    int out = bit.query(r) - bit.query(l - 1);
    int moves = r - l - 1 - out;
    if(v[l] > 0) moves++;
    ans += moves;

    bit.update(r, 1);
  }
  
  return ans;
}

// int32_t main(){
//   cout << count_swaps({2, 1, -1, -2}) << endl;
//   cout << count_swaps({-2, -1, 2, 1}) << endl;
//   cout << count_swaps({-2, 2, 2, -2, -2, 2}) << endl;
// }

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:34:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   34 |   for(auto [x, _] : id2pos[0]){
      |            ^
shoes.cpp:35:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(int i = 0; i < id2pos[0][x].size(); ++i){
      |                    ~~^~~~~~~~~~~~~~~~~~~~~
shoes.cpp:46:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   46 |   for(auto [l, r] : u){
      |            ^

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