Submission #443232

#	Time	Username	Problem	Language	Result	Execution time	Memory
443232		mkisic	Arranging Shoes (IOI19_shoes)	C++14	45 / 100	75 ms	12784 KiB

shoes

#include "shoes.h"
#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 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;
    }
  }

  long long inv = 0;
  loga.clear();

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

  return inv;
}


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

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