Submission #679677

#	Time	Username	Problem	Language	Result	Execution time	Memory
679677		tvladm2009	Coin Collecting (JOI19_ho_t4)	C++14	100 / 100	51 ms	1500 KiB

joi2019_ho_t4

#include <bits/stdc++.h>

using ll = long long;

int const nmax = 1e5;

int v[5 + nmax][3], s[3], wait[3];

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

  int n;
  std::cin >> n;
  ll result = 0;
  for(int i = 1;i <= 2 * n; i++) {
    int x, y;
    std::cin >> x >> y;
    if(x < 1) {
      result += 1 - x;
      x = 1;
    }
    if(x > n) {
      result += x - n;
      x = n;
    }
    if(y < 1) {
      result += 1 - y;
      y = 1;
    }
    if(y > 2) {
      result += y - 2;
      y = 2;
    }
    v[x][y]++;
  }

  int k1 = 1, k2 = 0;
  for(int i = 1;i <= n; i++)
    for(int j = 0;j < v[i][1] + v[i][2]; j++) {
      if(k1 < i)
        result += i - k1;
      else if(k1 > i)
        result += k1 - i;
      if(k2 > 0)
        k1++;
      k2 ^= 1;
    }
  for(int i = 1;i <= n; i++) {
    wait[1]++;
    wait[2]++;
    s[1] += v[i][1];
    s[2] += v[i][2];
    while(wait[1] > 0 && s[1] > 0) {
      wait[1]--;
      s[1]--;
    }
    while(wait[2] > 0 && s[2] > 0) {
      wait[2]--;
      s[2]--;
    }
    while(wait[1] > 0 && s[2] > 0) {
      result++;
      wait[1]--;
      s[2]--;
    }
    while(wait[2] > 0 && s[1] > 0) {
      result++;
      wait[2]--;
      s[1]--;
    }
  }
  std::cout << result;
  return 0;
}

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