Submission #127354

#	Time	Username	Problem	Language	Result	Execution time	Memory
127354		RockyB	Coin Collecting (JOI19_ho_t4)	C++17	100 / 100	92 ms	14316 KiB

joi2019_ho_t4

/// In The Name Of God

//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

#define f first
#define s second

#define pb push_back
#define pp pop_back
#define mp make_pair

#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()

#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, l, r) for (int i = (l); i >= (r); i--)

#define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

#define nl '\n'
#define ioi exit(0);

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int N = (int)2e5 + 7;
const int inf = (int)1e9 + 7;
const int mod = (int)1e9 + 7;
const ll linf = (ll)1e18 + 7;

const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};

using namespace std;

int n;
pair <ll, ll> a[N << 1];

ll dst(pair <ll, ll> x, pair <ll, ll> y) {
  return abs(x.f - y.f) + abs(x.s - y.s);
}

int cnt[N][3];

vector <int> em[3], fl[3];
ll calc(int v = 1) {
  if (v > n) return 0;
  ll res = 0;

  rep(j, 1, 2) {
    if (!cnt[v][j]) em[j].pb(v);
    if (cnt[v][j] > 1) fl[j].pb(v);
  }

  rep(j, 1, 2) {
    while (sz(em[j]) && cnt[v][j] > 1) {
      int p = em[j].back();
      if (!cnt[p][j]) {
        cnt[v][j]--;
        cnt[p][j]++;
        res += v - p;
        em[j].pp();
      }
      else em[j].pp();
    }
  }  
  rep(j, 1, 2) {
    if (!cnt[v][j]) {
      while (sz(fl[j])) {
        int p = fl[j].back();
        if (cnt[p][j] > 1) {
          res += v - p;
          cnt[p][j]--;
          cnt[v][j]++;
          if (cnt[p][j] == 1) fl[j].pp();
          break;
        }
        else fl[j].pp();
      }
    }
  }
  rep(j, 1, 2) {
    if (!cnt[v][j]) {
      while (sz(fl[3 - j])) {
        int p = fl[3 - j].back();
        if (cnt[p][3 - j] > 1) {
          res += v - p + 1;
          cnt[p][3 - j]--;
          cnt[v][j]++;
          if (cnt[p][3 - j] == 1) fl[3 - j].pp();
          break;
        }
        else fl[3 - j].pp();
      }
    }
  }
  rep(j, 1, 2) {
    while (sz(em[3 - j]) && cnt[v][j] > 1) {
      int p = em[3 - j].back();
      if (!cnt[p][3 - j]) {
        cnt[v][j]--;
        cnt[p][3 - j]++;
        res += v - p + 1;
        em[3 - j].pp();
      }
      else em[3 - j].pp();
    }
  }
  return res + calc(v + 1); 
}
int main() {
	#ifdef IOI
		freopen ("in.txt", "r", stdin);
    freopen ("D.out", "w", stdout);
	#endif
  Kazakhstan
  cin >> n;
  rep(i, 1, n << 1) {
    cin >> a[i].f >> a[i].s;
  }
  ll ans = 0;
  vector < pair <int, int > > to;
  to.pb({1, 1});
  to.pb({1, 2});
  to.pb({n, 1});
  to.pb({n, 2});
  rep(i, 1, n << 1) {
    ll mn = linf;
    pair <int, int> go = {-1, -1};
    
    to.pb({a[i].f, 2});
    to.pb({a[i].f, 1});
    to.pb({n, a[i].s});
    to.pb({1, a[i].s});

    for (auto it : to) {
      if (!(1 <= it.f && it.f <= n && 1 <= it.s && it.s <= 2)) {
        continue;
      }
      ll cur = dst(a[i], it);
      if (cur < mn) {
        mn = cur;
        go = it;
      }
    }
    rep(j, 1, 4) to.pp();
    ans += mn;
    cnt[go.f][go.s]++;
  }
  cout << ans + calc();
	ioi
}

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