Submission #598261

#	Time	Username	Problem	Language	Result	Execution time	Memory
598261		Sam_a17	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	511 ms	150404 KiB

shoes

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

#define sz(x) (int((x).size()))
#define len(x) (int)x.length()
#define all(x) (x).begin(), (x).end()
#define clr(x) (x).clear()
#define dbg(x) cout << #x << " " << x << endl;

#define ld long double
#define ll long long

void pr(vector<int>& a) {
  cerr << "[ ";
  for(auto i: a) {
    cerr << i << " ";
  }
  cerr << "]" << endl;
}

void pr(map<int, int>& mp) {
  cerr << "[ ";
  for(auto i: mp) {
    cerr << "{" << i.first << " " << i.second << "},";
  }
  cerr << "]" << endl;
}

struct fenwick {
  int size;
  vector<long long> tree;

  void init(int s) {
    tree.assign(s + 3, 0), size = s;
  }

  void upd(int u, long long v) {
    while(u <= size) {
      tree[u] += v;
      u += u & (-u);
    }
  }

  long long qry(int u) {
    long long sum = 0;
    while(u > 0) {
      sum += tree[u];
      u -= u & (-u);
    }
    return sum;
  }

  long long sum(int l, int r) {
    return qry(r) - qry(l - 1);
  }
} fn;


long long count_swaps(std::vector<int> S) {

  fn.init(sz(S) + 2);
  vector<pair<int, pair<int, int>>> order;

  map<int, deque<int>> mpall;
  for(int i = 0; i < sz(S); i++) {
    mpall[S[i]].push_back(i);

    if(!mpall[-S[i]].empty()) {
      // we found it
      if(S[i] < 0) {
        order.push_back({S[i], {mpall[S[i]].front(), mpall[-S[i]].front()}});
      } else {
        order.push_back({S[i], {mpall[-S[i]].front(), mpall[S[i]].front()}});
      }

      mpall[S[i]].pop_front();
      mpall[-S[i]].pop_front();
    }
  }

  int n = sz(S) / 2;
  ll answ = 0;
  for(int i = 0; i < sz(S); i += 2) {
    ll ft = order[i / 2].second.first + fn.sum(order[i / 2].second.first + 1, sz(S) + 2);
    ll sc = order[i / 2].second.second + fn.sum(order[i / 2].second.second + 1, sz(S) + 2);

    answ += abs(ft - i);
    if(ft > sc) {
      sc++;
    }
    answ += abs(sc - i - 1);

    // dbg(ft)
    // dbg(sc)

    fn.upd(order[i / 2].second.first + 1, 1);
    fn.upd(order[i / 2].second.second + 1, 1);
  }


  return answ;

}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:81:7: warning: unused variable 'n' [-Wunused-variable]
   81 |   int n = sz(S) / 2;
      |       ^

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