제출 #1146608

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1146608		fryingduc	Coin Collecting (JOI19_ho_t4)	C++20	0 / 100	0 ms	328 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];
int cnt[maxn];
int f[maxn];

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();
}

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];
  }
  long long res = 0;
  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]);
  }
  int zeros = 0;
  for (int i = 1; i <= n * 2; ++i) {
    if (!cnt[i]) ++zeros;
  }
  for (int t = 1; t <= n; ++t) {
    int z = (cnt[t] == 0) + (cnt[t + n] == 0);
    for (int i = t; i <= n + t; i += n) {
      if (cnt[i]) continue;
      pair<int, int> x = convert(i);
      int sum1 = 2e9;
      if (!fr[x.second].empty()) {
        sum1 = x.first - fr[x.second].back();
      }
      int sum2 = 2e9;
      if (!fr[x.second ^ 1].empty()) {
        sum2 = x.first - fr[x.second ^ 1].back() + 1;
      }
//      debug(i, sum1, sum2);
      if (sum1 < 2e9) {
        --cnt[fr[x.second].back() + x.second * n];
        ++cnt[i];
        --z;
        fr[x.second].pop_back();
        res += sum1;
      } else if (sum2 < 2e9) {
        if (z == 2 and calc() == 1) continue;
        --cnt[fr[x.second ^ 1].back() + (x.second ^ 1) * n];
        ++cnt[i];
        --z;
        fr[x.second ^ 1].pop_back();
        res += sum2;
      }
    }
    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);
      }
    }
    if (!z) continue;
    for (int i = t; i <= n + t; i += n) {
      if (cnt[i]) continue;
      pair<int, int> x = convert(i);
      int sum1 = 2e9;
      if (!fr[x.second].empty()) {
        sum1 = x.first - fr[x.second].back();
      }
      int sum2 = 2e9;
      if (!fr[x.second ^ 1].empty()) {
        sum2 = 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];
        --z;
        fr[x.second].pop_back();
        res += sum1;
      } else if (sum2 < 2e9) {
        if (z == 2 and calc() == 1) continue;
        --cnt[fr[x.second ^ 1].back() + (x.second ^ 1) * n];
        ++cnt[i];
        --z;
        fr[x.second ^ 1].pop_back();
        res += sum2;
      }
    }
  }
  for (int ite = 0; ite < 2; ++ite) {
    fr[ite].clear();
  }
//  debug(res);
  for (int t = n; t; --t) {
    int z = (cnt[t] == 0) + (cnt[t + n] == 0);
    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 i = t; i <= n + t; i += n) {
      if (cnt[i]) continue;
      pair<int, int> x = convert(i);
      int sum1 = 2e9;
      if (!fr[x.second].empty()) {
        sum1 = fr[x.second].back() - x.first;
      }
      int sum2 = 2e9;
      if (!fr[x.second ^ 1].empty()) {
        sum2 = fr[x.second ^ 1].back() - x.first + 1;
      }
      if (sum1 < 2e9 and sum1 <= sum2) {
        --cnt[fr[x.second].back() + x.second * n];
        ++cnt[i];
        --z;
        fr[x.second].pop_back();
        res += sum1;
      } else if (sum2 < 2e9) {
        if (z == 2 and calc() == 1) continue;
        --cnt[fr[x.second ^ 1].back() + (x.second ^ 1) * n];
        ++cnt[i];
        --z;
        fr[x.second ^ 1].pop_back();
        res += sum2;
      }
    }
  }
  cout << res;
}

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

  solve();

  return 0;
}
/*
3
-1 -1
-5 2
5 8
5 -8
8 -8
-4 7

5
-5 3
4 -6
1 -5
-1 7
1 -3
8 3
-8 -2
4 1
-4 4
3 8
*/

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