Submission #818178

#	Time	Username	Problem	Language	Result	Execution time	Memory
818178		christinelynn	Lasers (NOI19_lasers)	C++17	24 / 100	63 ms	5060 KiB

lasers

#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 (stderr)

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

• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 0 / 20
• Subtask 4: 0 / 21
• Subtask 5: 0 / 22
• Subtask 6: 0 / 13