oj.uz

Submission #631910

# Submission time Handle Problem Language Result Execution time Memory
631910 2022-08-19T06:29:32 Z Abrar_Al_Samit Coin Collecting (JOI19_ho_t4) C++17
0 / 100
 4 ms 360 KB 
#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]>1) 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;
    // for(int j=0; j<n; ++j) {
    //   cerr<<a[0][j]<<' '<<a[1][j]<<endl;
    // }
    // cerr<<"_____\n";
  }
  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;
  // } cerr<<"________\n";

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

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 4 ms 332 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 328 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 360 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 360 KB Output is correct
14 Incorrect 1 ms 212 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 4 ms 332 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 328 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 360 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 360 KB Output is correct
14 Incorrect 1 ms 212 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 4 ms 332 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 328 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 360 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 360 KB Output is correct
14 Incorrect 1 ms 212 KB Output isn't correct
15 Halted 0 ms 0 KB -