Submission #1244438

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244438		greenbinjack	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	194 ms	273648 KiB

shoes

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
 
#include <bits/stdc++.h>
using namespace std;
 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
 
using LL = long long;
 
#define all(V) V.begin(), V.end()
 
template <typename DT> using ordered_set = tree <DT, null_type, less <DT>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename DT> using minheap = priority_queue < DT, vector <DT>, greater <DT> >;
template <class T> bool chMax (T &x, T y) { return y > x ? x = y, 1 : 0; }
template <class T> bool chMin (T &x, T y) { return y < x ? x = y, 1 : 0; }

#include "shoes.h"

template <typename DT> class BIT {
  public:
    vector <DT> tree; 
    int n;
  BIT (int n) {
    this->n = n;
    tree.assign (n, 0);
  }
  BIT (const vector <DT> &a) : BIT (a.size()) {
    for (int i = 0; i < n; i++) add (i, a[i]);
  }
  DT sum (int r) {
    DT ret = 0;
    for (; r >= 0; r = (r & (r + 1)) - 1) ret += tree[r];
    return ret;
  }
  DT sum (int l, int r) {
    if (l > r) return 0;
    return sum(r) - sum(l - 1);
  }
  void add (int idx, DT delta) {
    for (; idx < n; idx = idx | (idx + 1)) tree[idx] += delta;
  } 
};
// BIT<LL> pref(mxN);

LL count_swaps (vector <int> S) {
  int n = S.size ();
  vector < queue <int> > left (n + 1), right (n + 1);
  for (int i = 0; i < n; i++) {
    if (S[i] < 0) left[-S[i]].push (i);
    else right[S[i]].push (i);
  }

  BIT<int> Tree (n);
  vector <int> visited (n);
  LL ans = 0;
  for (int i = 0; i < n; i++) {
    if (visited[i]) continue;
    int need = -S[i];
    if (need < 0) {
      int pos = left[-need].front ();
      left[-need].pop ();
      ans += pos - i - 1 - Tree.sum (i + 1, n - 1) + Tree.sum (pos + 1, n - 1) + 1;
      Tree.add (pos, +1);
      visited[pos] = 1;
      right[S[i]].pop ();
    } else {
      int pos = right[need].front ();
      right[need].pop ();
      ans += pos - i - 1 - Tree.sum (i + 1, n - 1) + Tree.sum (pos + 1, n - 1);
      Tree.add (pos, +1);
      visited[pos] = 1;
      left[-S[i]].pop ();
    }
  }

  return ans;
}

// int main() {
//   cin.tie (nullptr) -> ios_base ::  sync_with_stdio (false);

//   cout << count_swaps({-2, 2, 2, -2, -2, 2}) << '\n';

//   return 0;   
// } 

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