Submission #171727

#	Time	Username	Problem	Language	Result	Execution time	Memory
171727		AlexLuchianov	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	130 ms	22008 KiB

shoes

#include "shoes.h"
#include <cassert>
#include <iostream>

int const nmax = 200000;
using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

std::vector<int> left[1 + nmax];
std::vector<int> right[1 + nmax];
int v[1 + nmax], per[2][1 + nmax];

class FenwickTree{
private:
  int n;
  std::vector<int> aib;
public:
  FenwickTree(int n){
    aib.resize(1 + n);
    this->n = n;
  }
  void update(int x, int val){
    while(x <= n){
      aib[x] += val;
      x += (x ^ (x & (x - 1)));
    }
  }
  int query(int x){
    int result = 0;
    while(0 < x){
      result += aib[x];
      x = (x & (x - 1));
    }
    return result;
  }
};

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

	int n = s.size();
	for(int i = 1;i <= n; i++)
    v[i] = s[i - 1];
  for(int i = 1;i <= n; i++){
    if(v[i] < 0)
      left[-v[i]].push_back(i);
    else
      right[v[i]].push_back(i);
  }


  for(int i = 1;i <= n; i++){
    assert(left[i].size() == right[i].size());
    for(int h = 0;h < left[i].size(); h++){
      int x = left[i][h], y = right[i][h];
      per[0][x] = y;
      per[1][y] = x;
    }
  }
  FenwickTree aib(n);
  for(int i = 1;i <= n; i++)
    aib.update(i, 1);
  ll result = 0;
  for(int i = 1;i <= n; i++){
    if(v[i] < 0){
      if(i < per[0][i]){
        result += aib.query(per[0][i] - 1) - aib.query(i);
        aib.update(per[0][i], -1);
      }
    } else {
      if(i < per[1][i]){
        result += aib.query(per[1][i] - 1) - aib.query(i - 1);
        aib.update(per[1][i], -1);
      }
    }
  }
  return result;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:54:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0;h < left[i].size(); h++){
                   ~~^~~~~~~~~~~~~~~~

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