제출 #443230

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
443230		mkisic	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	1087 ms	8876 KiB

shoes

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

#define TRACE(x) cerr << #x << ' ' << x;
#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 = 100100;

int 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;
  REP(i, n) REP(j, i) inv += (pos[i] < pos[j]);

  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: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15