Submission #900744

#	Time	Username	Problem	Language	Result	Execution time	Memory
900744		cig32	Coin Collecting (JOI19_ho_t4)	C++17	0 / 100	20 ms	604 KiB

joi2019_ho_t4

#include "bits/stdc++.h"
using namespace std;
#define int long long
#define double long double
const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int bm(int b, int p) {
  if(p==0) return 1 % MOD;
  int r = bm(b, p >> 1);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
int inv(int b) { 
  return bm(b, MOD-2);
}
int fastlog(int x) {
  return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}
void printcase(int i) { cout << "Case #" << i << ": "; }
static void run_with_stack_size(void (*func)(void), size_t stsize) {
  char *stack, *send;
  stack = (char *)malloc(stsize);
  send = stack + stsize - 16;
  send = (char *)((uintptr_t)send / 16 * 16);
  asm volatile(
    "mov %%rsp, (%0)\n"
    "mov %0, %%rsp\n"
    :
    : "r"(send));
  func();
  asm volatile("mov (%0), %%rsp\n" : : "r"(send));
  free(stack);
}
int r[3][MAXN], l[3][MAXN], ud[3][MAXN];
void solve(int tc) { 
  int n;
  cin >> n;
  int cnt[3][n+1];
  for(int i=1; i<=3; i++) {
    for(int j=1; j<=n; j++) {
      cnt[i][j] = 0;
    }
  }
  int ans = 0;
  for(int i=1; i<=2*n; i++) {
    int x, y;
    cin >> x >> y;
    if(x < 1) ans += 1 - x;
    if(x > n) ans += x - n;
    if(y < 1) ans += 1 - y;
    if(y > 2) ans += y - 2;
    x = max(x, 1ll);
    y = max(y, 1ll);
    x = min(x, n);
    y = min(y, 2ll);
    cnt[y][x]++;
  }
  vector<pair<int, int> > extra;
  for(int i=1; i<=2; i++) {
    for(int j=1; j<=n; j++) {
      for(int k=1; k<cnt[i][j]; k++) extra.push_back({i, j});
    }
  }
  for(pair<int,int> x: extra) {
    int st = (x.first - 1) * n + x.second;
    vector<pair<int,int>> adj[2*n+1];
    for(int i=1; i<=2; i++) {
      for(int j=1; j<=n; j++) {
        int node = (i-1) * n + j;
        if(j>1 && l[i][j]>=r[i][j-1]) adj[node].push_back({node-1, 1});
        else if(j>1) adj[node].push_back({node-1, -1});
        if(j<n && r[i][j]>=l[i][j+1]) adj[node].push_back({node+1, 1});
        else if(j<n) adj[node].push_back({node+1, -1});
        if(ud[i][j]>=ud[3-i][j]) adj[node].push_back({(2-i)*n+j, 1});
        else adj[node].push_back({(2-i)*n+j, -1});
      }
    }
    bool vis[2*n+1];
    int dist[2*n+1], prv[2*n+1];
    for(int i=1; i<=2*n; i++) {
      dist[i] = 1e9;
      vis[i] = 0;
    }
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    dist[st] = 0;
    pq.push({0, st});
    while(pq.size()) {
      pair<int, int> t = pq.top();
      pq.pop();
      if(!vis[t.second]) {
        vis[t.second] = 1;
        for(pair<int, int> x : adj[t.second]) {
          if(!vis[x.first] && dist[x.first] > dist[t.second] + x.second) {
            dist[x.first] = dist[t.second] + x.second;
            prv[x.first] = t.second;
            pq.push({dist[x.first], x.first});
          }
        }
      }
    }
    int en = -1, mn = 1e9;
    for(int i=1; i<=2; i++) {
      for(int j=1; j<=n; j++) {
        if(!cnt[i][j]) {
          int id = (i-1) * n + j;
          if(dist[id] < mn) {
            mn = dist[id];
            en = id;
          }
        }
      }
    }
    cnt[(st-1)/n+1][(st-1)%n+1]--;
    cnt[(en-1)/n+1][(en-1)%n+1]++;
    //cout<<st<<" -> "<<en<<"\n";
    ans += dist[en];
    while(en != st) {
      int p = prv[en];
      if(p + n == en) {
        ud[1][p]++;
      }
      else if(p - n == en) {
        ud[2][p-n]++;
      }
      else if(p + 1 == en) {
        if(p <= n) r[1][p]++;
        else r[2][p-n]++;
      }
      else {
        if(p <= n) l[1][p]++;
        else l[2][p-n]++;
      }
      en = p;
    }
    
  }
  cout << ans << "\n";
}

void uwu() {
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}
int32_t main() {
  #ifdef ONLINE_JUDGE
  uwu();
  #endif
  #ifndef ONLINE_JUDGE
  run_with_stack_size(uwu, 1024 * 1024 * 1024); // run with a 1 GiB stack
  #endif
}
/*
g++ A.cpp -std=c++17 -O2 -o A
./A < input.txt


*/

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