Submission #443261

#	Time	Username	Problem	Language	Result	Execution time	Memory
443261		mkisic	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	180 ms	17696 KiB

shoes

#include "shoes.h"
#include <cassert>
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

#define TRACE(x) cerr << #x << ' ' << x << endl
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define _ <<  " " << 

#define pb push_back

const int MAXN = 200100;

struct Fenwick {
  int p[MAXN];
  
  void clear() {
    memset(p, 0, sizeof p);
  }

  void add(int x) {
    for (int i = x; i > 0; i -= i &- i) 
      p[i]++;
  }

  int get(int x) {
    int ret = 0;
    for (int i = x; i < MAXN; i += i &- i)
      ret += p[i];
    return ret;
  }
}loga;

long long get_inv(vector <int> pos) {
  long long inv = 0;
  loga.clear();

  REP(i, pos.size()) {
    inv += loga.get(pos[i] + 1);
    loga.add(pos[i] + 1);
  }
  return inv;
}


long long solve(vector <int> p, int start, int T) {
  vector <int> pos;
  vector <int> v[MAXN];
  int n = p.size();
  pos.resize(n);
  int t = start;
  REP(i, n) {
    if (p[i]/abs(p[i]) == T) {
      v[max(p[i], -p[i])].pb(t);
      pos[i] = t;
      t += 2;
    }
  }
  
  REP(i, MAXN) reverse(v[i].begin(), v[i].end());

  REP(i, n) {
    if (p[i]/abs(p[i]) != T) {
      int x = v[max(p[i], -p[i])].back();
      v[max(p[i], -p[i])].pop_back();
      if (p[i] < 0) x--;
      else x++;
      pos[i] = x;
    }
  }

  return get_inv(pos);
}

long long f(vector <int> p) {
  int n = p.size() / 2;
  vector <int> r;
  vector <int> v[MAXN];
  REP(i, 2 * n) {
    int a = p[i] + n;
    int b = p[i];
    if (p[i] < 0) {
      a = abs(p[i]);
      b = a + n;
    }
    if (v[b].empty()) {
      v[a].pb(i);
      r.pb(abs(p[i]));
    } else v[b].pop_back(); 
  }

  REP(i, MAXN) assert(v[i].empty());

  REP(i, 2 * n) {
    int x = p[i] + n;
    if (p[i] < 0) x = abs(p[i]);
    v[x].pb(i);
  }

  REP(i, MAXN) reverse(v[i].begin(), v[i].end());
  
  vector <int> pos;
  pos.resize(p.size());

  int t = 0;
  REP(i, n) {
    pos[v[r[i]].back()] = t++;
    v[r[i]].pop_back();
    pos[v[r[i] + n].back()] = t++;
    v[r[i] + n].pop_back();
  }

  return get_inv(pos);
}


long long count_swaps(std::vector<int> s) {
  return min(min(solve(s, 0, -1), solve(s, 1, 1)), f(s));
}

Compilation message (stderr)

shoes.cpp: In function 'long long int get_inv(std::vector<int>)':
shoes.cpp:10:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 | #define FOR(i, a, b) for (int i = (a); i < (b); i++)
      |                                          ^
shoes.cpp:11:19: note: in expansion of macro 'FOR'
   11 | #define REP(i, n) FOR(i, 0, n)
      |                   ^~~
shoes.cpp:42:3: note: in expansion of macro 'REP'
   42 |   REP(i, pos.size()) {
      |   ^~~

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