Submission #411388

#	Time	Username	Problem	Language	Result	Execution time	Memory
411388		ollel	Arranging Shoes (IOI19_shoes)	C++17	50 / 100	1083 ms	19912 KiB

shoes

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

#define rep(i,a,b) for(int i = a; i < b; i++)
#define pb push_back

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;

ll ans = 0;
int n;
vi shoes;

int f(int x, int m) {
  return (x > 0) ? x : m - 1 + x;
}

void rem() {
  int pairs = n/2;
  rep(pair, 0, pairs) {

    vi dist(pairs, 0);
    rep(i,0,n) dist[shoes[i]] += i;
    int bd = 1e9, p;
    rep(i, 0, pairs) {
      if (dist[i] < bd) {bd = dist[i]; p = i;}
    }

    ans += bd - 1;
    rep(i, 0, n-1) if (shoes[i] == p) swap(shoes[i], shoes[i + 1]);
    rep(i, 0, n-1) if (shoes[i] == p) swap(shoes[i], shoes[i + 1]);

  }
}

ll count_swaps(vi S)
{
  n = S.size(); shoes.resize(n); rep(i,0,n) shoes[i] = S[i];
  rep(i,0,n) shoes[i] = -shoes[i];

  vvi exists(2*n + 5);
  rep(i,0,n) exists[f(shoes[i], 2*n+5)].pb(i);
  int real = 0;

  rep(i,1,n+1) {
    rep(j, 0, (int)exists[i].size()) {
      int a = exists[i][j], b = exists[f(-i, 2*n+5)][j];
      if (a > b) ans++;
      shoes[a] = shoes[b] = real;
      real++;
    }
  }
  rem();
  return ans;
}

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