Submission #631827

#	Time	Username	Problem	Language	Result	Execution time	Memory
631827		Abrar_Al_Samit	Coin Collecting (JOI19_ho_t4)	C++17	0 / 100	1 ms	212 KiB

joi2019_ho_t4

#include<bits/stdc++.h>
using namespace std;
const int MX = 1e5 + 5;
const int INF = 1e9;
int n;
int a[2][MX];

int nxt(int i, int j) {
  for(; j<n; ++j) {
    if(a[i][j]) return j;
  }
  return INF;
}
long long solve() {
  int rem1 = accumulate(a[0], a[0]+n, 0), rem2 = accumulate(a[1], a[1]+n, 0);
  long long ret = 0;
  for(int i=0; i<n-1; ++i) {
    if(a[0][i]>0 && a[1][i]>0) {
      ret += a[0][i]-1 + a[1][i]-1;
      a[0][i+1] += a[0][i]-1;
      a[1][i+1] += a[1][i]-1;

      a[0][i] = a[1][i] = 1;
    }
    if(a[0][i]==0 && a[1][i]==0) {
      int j=nxt(0, i+1), k=nxt(1, i+1);

      if(j<k) {
        a[0][j]--, a[0][i]++;
        ret += j-i;
      } else {
        a[1][k]--, a[1][i]++;
        ret += k-i;
      }
    } 
    if(a[0][i]==0) {
      if(a[1][i]>1) {
        --rem2;
        ++rem1;
        a[1][i]--, a[0][i]++;
        ret += 1;
        goto outside;
      }

      int j=nxt(0, i+1), k=nxt(1, i+1);
      if(j>k+1 || (j==k+1 && rem1<rem2)) {
        ret += k-i+1;
        ++rem1;
        --rem2;
        a[1][k]--, a[0][i]++;
      } else {
        ret += j-i;
        a[0][j]--, a[0][i]++;
      }
    } outside:

    if(a[1][i]==0) {
      if(a[0][i]>1) {
        --rem1, ++rem2;
        a[0][i]--, a[1][i]++;
        ret += 1;
        goto outside2;
      }

      int j=nxt(0, i+1), k=nxt(1, i+1);
      if(j+1<k || (j+1==k && rem2<rem1)) {
        ret += j-i+1;
        --rem1;
        ++rem2;
        a[0][j]--, a[1][i]++;
      } else {
        ret += k-i;
        a[1][k]--, a[1][i]++;
      }
    } outside2:
    if(a[0][i]>1) {
      a[0][i+1] += a[0][i]-1;
      ret += a[0][i]-1;
    }
    if(a[1][i]>1) {
      a[1][i+1] += a[1][i]-1;
      ret += a[1][i]-1;
    }
    --rem1, --rem2;
    //cerr<<ret<<endl;
  }
  if(~a[0][n-1]&1) ++ret;
  return ret;
}
void PlayGround() {
  cin>>n;
  long long cost = 0;
  for(int i=0; i<2*n; ++i) {
    int x, y;
    cin>>x>>y;
    swap(x, y);
    if(x<=1) {
      cost += 1-x;
      x = 0;
    } else {
      cost += x-2;
      x = 1;
    }
    if(y<1) {
      cost += 1-y;
      y = 1;
    }
    if(y>n) {
      cost += y-n;
      y = n;
    }
    --y;
    a[x][y]++;
  }    

  // cerr<<cost<<endl;
  // for(int i=0; i<n; ++i) {
  //   cerr<<a[0][i]<<' '<<a[1][i]<<endl;
  // }

  cout<<solve()+cost<<'\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  PlayGround();
  return 0;
}

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