Submission #1245159

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245159		hayford08	Nile (IOI24_nile)	C++20	67 / 100	2095 ms	5448 KiB

nile

#include <iostream>
#include <vector>
#include <ranges>
#include <algorithm>
#include <numeric>
#include <set>
using namespace std;

vector<long long> subTask1(long long base, const vector<int> &W, const vector<int> &C, const vector<int> &E) {
  int n = W.size(), q = E.size();
  if (n % 2 == 0) {
    return vector<long long>(q, base);
  }
  int mn = *min_element(C.begin(), C.end());
  return vector<long long>(q, base + mn);
}

vector<long long> subTask2(long long base, const vector<int> &W, const vector<int> &C, const vector<int> &E) {
  int n = W.size(), q = E.size();
  if (n % 2 == 0) {
    return vector<long long>(q, base);
  }
  vector<long long> ans(q);
  int mn = *min_element(C.begin(), C.end());
  for (int i = 0; i < q; i++) {
    long long cost = 1e18;
    if (E[i] == 1) {
      int curr = 1e9;
      for (int j = 0; j < n; j += 2) {
        curr = min(curr, C[j]);
      }
      cost = base + curr;
    }
    else {
      cost = base + mn;
    }
    ans[i] = cost;
  }
  return ans;
}

vector<long long> subTask3(long long base, vector<int> &W, const vector<int> &E) {
  int q = E.size(), n = W.size();
  vector<long long> ans(q);
  ranges::sort(W);
  for (int i = 0; i < q; i++) {
    int D = E[i];
    long long cost = base;
    int pos = 0;
    while (pos < n){
      int cnt = 0;
      int w = W[pos];
      while (pos < n && W[pos] - w <= D) {
        cnt++;
        w = W[pos++];
      }
      cost += (cnt & 1);
    }
    ans[i] = cost;
  }
  return ans;
}

vector<long long> subTask5(const vector<int> &W, const vector<int> &A, const vector<int> &B, const vector<int> &E) {
  int n = W.size();
  vector<array<int, 2>> arr(n);
  long long base = 0;
  for (int i = 0; i < n; i++) {
    arr[i] = {W[i], A[i] - B[i]};
    base += B[i];
  }
  ranges::sort(arr);

  auto compute = [&](int l, int r, int D) -> long long { 
    int len = r - l + 1;
    if (len % 2 == 0) {
      return 0LL;
    }
    int cost = 1e9;
    for (int i = l; i <= r; i++) {
      // remove i 
      int szLeft = i - l;
      if ((szLeft % 2 == 0) || (i - 1 >= l && i + 1 <= r && arr[i + 1][0] - arr[i - 1][0] <= D)) {
        cost = min(cost, arr[i][1]);
      }
      // (pair i - 1 and i) or (i and i + 1)
      else {
        cost = min(cost, min(arr[i - 1][1], arr[i + 1][1]));
      }
    }
    return cost;
  };

  int q = E.size();
  vector<long long> res(q, base);
  for (int i = 0; i < q; i++) {
    int D = E[i];
    int pos = 0;
    while (pos < n) {
      int l = pos, r = pos++;
      while (pos < n && arr[pos][0] - arr[pos - 1][0] <= D) {
        r = pos++;
      }
      res[i] += compute(l, r, D);
    }
  }
  return res;
}


std::vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
  int n = (int)W.size();
  long long base = accumulate(B.begin(), B.end(), 0LL);
  vector<int> C(n);
  for (int i = 0; i < n; i++) {
    C[i] = A[i] - B[i];
  }
  if (*max_element(W.begin(), W.end()) == 1) {
    return subTask1(base, W, C, E);
  }
  bool isSubTask2 = true;
  for (int i = 0; i < n && isSubTask2; i++) {
    isSubTask2 &= (W[i] == i + 1);
  }
  if (isSubTask2) {
    return subTask2(base, W, C, E);
  }
  return subTask5(W, A, B, E);
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 11 / 11
• Subtask 5: 20 / 20
• Subtask 6: 0 / 15
• Subtask 7: 0 / 18