Submission #1047348

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047348		MercubytheFirst	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	47 ms	15308 KiB

shoes

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

long long inversion_count(vector<int> v) {
  ll ans = 0;
  int n = v.size();
  for(int& i : v)
    i += 1;
  int bit[n + 1]{};
  for(int i = 0; i < n; ++i) {
    assert(1 <= v[i] and v[i] <= n);
    for(int idx = n; idx > 0; idx -= (idx&-idx)) {
      ans += bit[idx];
    }
    for(int idx = v[i]; idx > 0; idx -= (idx&-idx)) {
      ans -= bit[idx];
    }
    for(int idx = v[i]; idx <= n; idx += (idx&-idx)) {
      bit[idx]++;
    }
  }
  return ans;
}


long long count_swaps(std::vector<int> s) {
  // ll ans = 0;
  int n = (int)s.size() / 2;
  vector<vector<int> > r(n + 1), l(n + 1);
  for(int i = 0; i < 2*n; ++i) {
    if(s[i] < 0) {
      l[abs(s[i])].push_back(i);
    }
    else {
      r[s[i]].push_back(i);
    }
  }
  for(int i = 1; i <= n; ++i) {
    reverse(l[i].begin(), l[i].end());
    reverse(r[i].begin(), r[i].end());
  }
  vector<int> order(2*n, -1);
  vector<bool> used(2*n, false);
  int idx = 0;
  for(int i = 0; i < 2*n; ++i) {
    if(used[i]) {
      continue;
    }
    const int sz = abs(s[i]);
    int lshoe, rshoe;
    if(s[i] < 0) {
      lshoe = i;
      rshoe = r[sz].back();
      while(used[rshoe]) {
        r[sz].pop_back();
        rshoe = r[sz].back();
      }
      r[sz].pop_back();
    }
    else if(s[i] > 0) {
      rshoe = i;
      lshoe = l[sz].back();
      while(used[lshoe]) {
        l[sz].pop_back();
        lshoe = l[sz].back();
      }
      l[sz].pop_back();
    }
    else assert(false);
    assert(!used[lshoe] and !used[rshoe]);
    assert(order[lshoe] == -1 and order[rshoe] == -1);
    used[lshoe] = used[rshoe] = true;
    order[lshoe] = idx;
    order[rshoe] = idx+1;
    idx += 2;
  }
  // for(int x : order)
  //   cout << x << ' ';
  // cout << endl;
  return inversion_count(order);
}

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