Submission #420589

#	Time	Username	Problem	Language	Result	Execution time	Memory
420589		SSRS	Arranging Shoes (IOI19_shoes)	C++14	65 / 100	144 ms	5064 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000;
struct binary_indexed_tree{
  int N;
  vector<int> BIT;
  binary_indexed_tree(int N): N(N), BIT(N + 1, 0){
  }
  void add(int i, int x){
    i++;
    while (i <= N){
      BIT[i] += x;
      i += i & -i;
    }
  }
  int sum(int i){
    int ans = 0;
    while (i > 0){
      ans += BIT[i];
      i -= i & -i;
    }
    return ans;
  }
  int sum(int L, int R){
    return sum(R) - sum(L);
  }
};
long long count_swaps(vector<int> S){
  int n = S.size() / 2;
  if (n <= 8){
    vector<int> p;
    for (int i = 0; i < n * 2; i++){
      if (S[i] > 0){
        p.push_back(S[i]);
      }
    }
    sort(p.begin(), p.end());
    int ans = INF;
    while (true){
      map<int, queue<int>> Q;
      for (int i = 0; i < n; i++){
        Q[-p[i]].push(i * 2);
        Q[p[i]].push(i * 2 + 1);
      }
      vector<int> p2(n * 2);
      for (int i = 0; i < n * 2; i++){
        p2[i] = Q[S[i]].front();
        Q[S[i]].pop();
      }
      int cnt = 0;
      for (int i = 0; i < n * 2; i++){
        for (int j = i + 1; j < n * 2; j++){
          if (p2[i] > p2[j]){
            cnt++;
          }
        }
      }
      ans = min(ans, cnt);
      if (!next_permutation(p.begin(), p.end())){
        break;
      }
    }
    return ans;
  } else {
    bool subtask3 = true;
    for (int i = 0; i < n * 2 - 1; i++){
      if (abs(S[i]) != abs(S[i + 1])){
        subtask3 = false;
      }
    }
    if (subtask3){
      int x = abs(S[0]);
      map<int, queue<int>> Q;
      for (int i = 0; i < n; i++){
        Q[-x].push(i * 2);
        Q[x].push(i * 2 + 1);
      }
      vector<int> p(n * 2);
      for (int i = 0; i < n * 2; i++){
        p[i] =  Q[S[i]].front();
        Q[S[i]].pop();
      }
      binary_indexed_tree BIT(n * 2);
      long long ans = 0;
      for (int i = 0; i < n * 2; i++){
        ans += BIT.sum(p[i], n * 2);
        BIT.add(p[i], 1);
      }
      return ans;
    } else {
      for (int i = 0; i < n; i++){
        assert(S[i] < 0 && S[n + i] > 0 && S[i] == -S[n + i]);
      }
      return (long long) n * (n - 1) / 2;
    }
  }
}

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