Submission #1146623

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146623		fryingduc	Coin Collecting (JOI19_ho_t4)	C++20	100 / 100	28 ms	5056 KiB

joi2019_ho_t4

#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 2e5 + 5;
const long long inf = 1e12;
int n, x[maxn], y[maxn];
int cls[maxn];
vector<int> fr[2];
vector<int> zeros[2];
int cnt[maxn];
int f[maxn];
long long res;

pair<int, int> convert(int id) {
  if (id > n) {
    return make_pair(id - n, 1);
  } 
  return make_pair(id, 0);
}

int calc() {
  return (int)fr[0].size() + (int)fr[1].size();
}

bool pri_op(int i) {
  pair<int, int> x = convert(i);
  int sum1 = 2e9;
  if (!fr[x.second].empty()) {
    sum1 = abs(x.first - fr[x.second].back());
  }
  if (sum1 < 2e9) {
    debug(i, sum1);
    --cnt[fr[x.second].back() + x.second * n];
    ++cnt[i];
    fr[x.second].pop_back();
    res += sum1;
    return 1;
  }
  return 0;
}

bool op(int i) {
  pair<int, int> x = convert(i);
  int sum1 = 2e9;
  if (!fr[x.second].empty()) {
    sum1 = abs(x.first - fr[x.second].back());
  }
  int sum2 = 2e9;
  if (!fr[x.second ^ 1].empty()) {
    sum2 = abs(x.first - fr[x.second ^ 1].back()) + 1;
  }
  debug(i, sum1, sum2);
  if (sum1 < 2e9 and sum1 <= sum2) {
    --cnt[fr[x.second].back() + x.second * n];
    ++cnt[i];
    fr[x.second].pop_back();
    res += sum1;
    return 1;
  } else if (sum2 < 2e9) {
    --cnt[i];
    res += sum2;
    fr[x.second ^ 1].pop_back();
    return 1;
  }
  return 0;
}

void solve() {
  cin >> n;
  int corner_x[] = {1, 1, n, n};
  int corner_y[] = {0, 1, 0, 1};
  int corner_id[] = {1, n + 1, n, n + n};
  for (int i = 1; i <= n + n; ++i) {
    cin >> x[i] >> y[i];
    --y[i];
  }
  for (int i = 1; i <= n + n; ++i) {
    if (x[i] >= 1 and x[i] <= n) {
      cls[i] = (y[i] < 1 ? x[i] : x[i] + n);
    } else {
      long long mn = inf, opt = -1;
      for (int c = 0; c < 4; ++c) {
        long long dist = abs(corner_x[c] - x[i]) + abs(corner_y[c] - y[i]);
        if (dist < mn) {
          mn = dist, opt = c;
        }
      }
      cls[i] = corner_id[opt];
    }
    ++cnt[cls[i]];
    pair<int, int> t = convert(cls[i]);
    res += abs(t.first - x[i]) + abs(t.second - y[i]);
    debug(i, res, cls[i]);
  }
  for (int t = 1; t <= n; ++t) {
    for (int i = t; i <= n + t; i += n) {
      if (cnt[i]) continue;
      pri_op(i);
    }
    for (int i = t; i <= n + t; i += n) {
      pair<int, int> x = convert(i);
      for (int j = 2; j <= cnt[i]; ++j) {
        fr[x.second].push_back(x.first);
      }
    }
    for (int ite = 0; ite < 2; ++ite) {
      while (!zeros[ite].empty()) {
        if (pri_op(zeros[ite].back())) {
          zeros[ite].pop_back();
        } else break;
      }
    }
    for (int i = t; i <= n + t; i += n) {
      if (cnt[i]) continue;
      if (!op(i)) {
        zeros[convert(i).second].push_back(i);
      }
    }
    for (int ite = 0; ite < 2; ++ite) {
      while (!zeros[ite].empty()) {
        if (op(zeros[ite].back())) {
          zeros[ite].pop_back();
        } else break;
      }
    }
  }
  cout << res;
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}
/*
10
9 448313173
948231962 688083351
3 -892902880
8 -284221198
2 658009446
8 -603114632
3 415052581
4 535391558
8 -350163427
939140935 -609372949
5 210609765
3 103753067
4 -664786740
3 -947786695
4 -173590153
5 519953525
2 838539928
2 608831779
4 -15820981
4 -350557357

*/

• Subtask 1: 8 / 8
• Subtask 2: 29 / 29
• Subtask 3: 63 / 63