oj.uz

Submission #818178

# Submission time Handle Problem Language Result Execution time Memory
818178 2023-08-10T03:17:16 Z christinelynn Lasers (NOI19_lasers) C++17
24 / 100
 63 ms 5060 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
void print(ll Z) { cout << Z << endl; }
void print(string S) { cout << S << endl; }
ll L, R;
vector<ll> V1;
vector<ll> V2;
ll X1, X2;
ll totalX1 = 0;
ll totalX2 = 0;
ll maxZA = -1;
ll maxZ = 0;
ll maxA = 0;
pair<ll, ll> range1;
pair<ll, ll> range2;
ll work3a() {
  if (maxZ < L / 2) {
    return 0;
  } else {
    if (L % 2) {
      ll blocked = L - 2 * (L - totalX1);
      ll cnt = 0;
      ll idx = 0;
      ll N = (totalX1 - (L / 2)) * 2 - 1;
      range1.second = (L / 2) - (N / 2);
      while (cnt <= (N)) {
        cnt += V1[idx];
        if (cnt <= (totalX1 - (L / 2)) * 2) {
          blocked = max(0LL, blocked - V1[idx]);
          range1.second += V1[idx];
        }
        idx++;
      }
      cnt = L;
      idx = X1;
      range1.first = L / 2 + N / 2;
      while (cnt > (N)) {
        cnt -= V1[idx];
        if (cnt > (totalX1 - (L / 2)) * 2) {
          blocked = max(0LL, blocked - V1[idx]);
          range1.first -= V1[idx];
        }
        idx++;
      }

      return blocked;
    } else {
      ll blocked = L - 2 * (L - totalX1);
      ll cnt = 0;
      ll idx = 0;
      ll N = (totalX1 - (L / 2)) * 2;
      range1.second = (L / 2) - (N / 2);
      while (cnt <= (N)) {
        cnt += V1[idx];
        if (cnt <= (totalX1 - (L / 2)) * 2) {
      blocked = max(0LL, blocked - V1[idx]);
          range1.second += V1[idx];
        }
        idx++;
      }
      cnt = L;
      idx = X1;
      range1.first = L / 2 + N / 2;
      while (cnt > (N)) {
        cnt -= V1[idx];
        if (cnt > N) {
          blocked = max(0LL, blocked - V1[idx]);
          range1.first -= V1[idx];
        }
        idx++;
      }

      return blocked;
    }
  }
}
ll work3b() {
  if (maxA < L / 2) {
  print(maxA);
    return 0;
  } else {
    if (L % 2) {
      ll blocked = L - 2 * (L - totalX2);
      ll cnt = 0;
      ll idx = 0;
      ll N = (totalX2 - (L / 2)) * 2 - 1;
      range2.second = (L / 2) - (N / 2);
      while (cnt <= (N)) {
        cnt += V2[idx];
        if (cnt <= (totalX1 - (L / 2)) * 2) {
          blocked = max(0LL, blocked - V2[idx]);
          range2.second += V2[idx];
        }
        idx++;
      }
      cnt = L;
      idx = X2;
      range2.first = L / 2 + N / 2;
      while (cnt > (N)) {
        cnt += V2[idx];
        if (cnt <= (N)) {
          blocked = max(0LL, blocked - V2[idx]);
          range2.first -= V2[idx];
        }
        idx++;
      }

      return blocked;
    } else {
      ll blocked = L - 2 * (L - totalX2);
      ll cnt = 0;
      ll idx = 0;
      ll N = (totalX2 - (L / 2)) * 2;
      range2.second = (L / 2) - (N / 2);
      while (cnt <= (N)) {
        cnt += V2[idx];
        if (cnt <= (N)) {
          blocked = max(0LL, blocked - V2[idx]);
          range2.second += V2[idx];
        }
        idx++;
      }
      cnt = L;
      idx = X1;
      range2.first = L / 2 + N / 2;
      while (cnt > (N)) {
        cnt -= V2[idx];
        if (cnt > N) {
          blocked = max(0LL, blocked - V2[idx]);
          range2.first -= V2[idx];
        }
        idx--;
      }

      return blocked;
    }
  }
}
ll work3() {
  if (totalX1 <= L / 2 and totalX2 <= L / 2) {
    return 0;
  } else if (X1 == 1 and X2 == 1) {
    return ((maxZA - (L / 2)) * 2 - 1);
  } else if (totalX1 > L / 2 and totalX2 <= L / 2) {
    return work3a();
  } else if (totalX2 > L / 2 and totalX1 <= L / 2) {
    if (maxA < L / 2) {
      return 0;
    } else {
      return work3b();
    }
  } else {
    if (maxZ <= L / 2 and maxA <= L / 2) {
      return 0;
    } else {
      ll B = work3a();
      ll C = work3b();
      if (B == 0 and C == 0) {
        return 0;
      } else if (B == 0) {
        return C;
      } else if (C == 0) {
        return B;
      }
      if (range2.first > range1.first) {
        return range2.first - range1.second + 1;
      } else {
        return range1.first - range2.second + 1;;
      }
    }
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> L >> R;
  if (R == 1) {
    // Subtask 1
    ll X;
    cin >> X;
    if (X == 1) {
      ll Y;
      cin >> Y;
      if (Y > L / 2) {
        if (L % 2)
          print((Y - (L / 2)) * 2 - 1);
        else
          print((Y - (L / 2)) * 2);
      } else
        print(0);
    }
  } else if (R == 2) {
    // Subtask 3
    cin >> X1;
    for (int i = 0; i < X1; i++) {
      ll Z;
      cin >> Z;
      V1.push_back(Z);
      totalX1 += Z;
      maxZA = max(maxZA, Z);
    }
    maxZ = maxZA;
    cin >> X2;
    for (int i = 0; i < X2; i++) {
      ll A;
      cin >> A;
      V2.push_back(A);
      totalX2 += A;
      maxZA = max(maxZA, A);
      maxA = max(A, maxA);
    }
    ll ans = work3();
    print(ans);
  } else {
    ll ans = 0;
    ll maxY = 0;
    while (R--) {
      ll X;
      cin >> X;
      if (X == 1) {
        // Subtask 2
        ll Y;
        cin >> Y;
        maxY = max(maxY, Y);
      }
    }
    if (maxY > L / 2) {
      if (L % 2)
        print((maxY - (L / 2)) * 2 - 1);
      else
        print((maxY - (L / 2)) * 2);
    } else
      print(0);
  }
  return 0;
}

Compilation message

lasers.cpp: In function 'int main()':
lasers.cpp:217:8: warning: unused variable 'ans' [-Wunused-variable]
  217 |     ll ans = 0;
      |        ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 328 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 292 KB Output is correct
10 Correct 0 ms 212 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 328 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 292 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 63 ms 812 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 53 ms 812 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 5060 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 5060 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 328 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 292 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 63 ms 812 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 53 ms 812 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Incorrect 18 ms 5060 KB Output isn't correct
22 Halted 0 ms 0 KB -