Submission #222843

#	Time	Username	Problem	Language	Result	Execution time	Memory
222843		rama_pang	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	125 ms	15856 KiB

shoes

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

class BIT {
 private:
  vector<int> tree;

 public:
  BIT() {}
  BIT(int n) { tree.assign(n, 0); }

  void Update(int p, int x) {
    for (int i = p + 1; i <= tree.size(); i += (i & -i)) {
      tree[i - 1] += x;
    }
  }

  int Query(int p) {
    int res = 0;
    for (int i = p + 1; i > 0; i -= (i & -i)) {
      res += tree[i - 1];
    }
    return res;
  }
};

long long count_swaps(vector<int> S) {
  int N = S.size() / 2;
  vector<vector<int>> ShoeSizeLeft(N + 1);
  vector<vector<int>> ShoeSizeRight(N + 1);
  vector<pair<int, int>> arrange;

  for (int i = 0; i < 2 * N; i++) {
    if (S[i] < 0) { // Left Shoe
      ShoeSizeLeft[-S[i]].emplace_back(i);
    } else { // Right Shoe
      ShoeSizeRight[S[i]].emplace_back(i);
    }
  }

  long long Answer = 0;

  for (int i = 1; i <= N; i++) {
    for (int j = 0; j < (int) ShoeSizeLeft[i].size(); j++) {
      arrange.emplace_back(ShoeSizeLeft[i][j], ShoeSizeRight[i][j]);
      if (arrange.back().first > arrange.back().second) {
        swap(arrange.back().first, arrange.back().second); // Swap Left and Right Shoe
        Answer++;
      }
    }
  }

  BIT tree(2 * N);
  for (int i = 1; i < 2 * N; i++) {
    tree.Update(i, 1);
  }

  sort(begin(arrange), end(arrange));  
  for (int i = 0; i < N; i++) {
    int L = arrange[i].first;
    int R = arrange[i].second;
    Answer += tree.Query(L);
    Answer += tree.Query(R) - 1;

    // Move position L to 0
    tree.Update(0, 1);
    tree.Update(L, -1);

    // Delete position R to 1
    tree.Update(1, 1);
    tree.Update(R, -1);

    // Delete position 0 and 1
    tree.Update(0, -2);
  }

  return Answer;
}

Compilation message (stderr)

shoes.cpp: In member function 'void BIT::Update(int, int)':
shoes.cpp:14:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = p + 1; i <= tree.size(); i += (i & -i)) {
                         ~~^~~~~~~~~~~~~~

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