Submission #420624

#	Time	Username	Problem	Language	Result	Execution time	Memory
420624		SSRS	Arranging Shoes (IOI19_shoes)	C++14	85 / 100	49 ms	4276 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 <= 1000){
    vector<int> a, b;
    map<int, queue<int>> Q;
    for (int i = 0; i < n * 2; i++){
      if (Q[-S[i]].empty()){
        Q[S[i]].push(i);
      } else {
        a.push_back(Q[-S[i]].front());
        b.push_back(i);
        Q[-S[i]].pop();
      }
    }
    int ans = 0;
    for (int i = 0; i < n; i++){
      for (int j = i + 1; j < n; j++){
        if (a[i] < a[j] && a[j] < b[i] && b[i] < b[j]){
          ans++;
        }
        if (a[j] < a[i] && a[i] < b[j] && b[j] < b[i]){
          ans++;
        }
        if (a[i] < a[j] && b[j] < b[i]){
          ans += 2;
        }
        if (a[j] < a[i] && b[i] < b[j]){
          ans += 2;
        }
      }
    }
    for (int i = 0; i < n; i++){
      if (S[a[i]] > 0){
        ans++;
      }
    }
    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: 20 / 20
• Subtask 6: 0 / 15