Submission #881317

#	Time	Username	Problem	Language	Result	Execution time	Memory
881317		nima_aryan	Naan (JOI19_naan)	C++17	0 / 100	1 ms	348 KiB

naan

/**
 *    author:  NimaAryan
 *    created: 2023-12-01 08:14:38  
**/
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#endif

using i64 = long long;

constexpr i64 inf = 1E14;

struct Z {
  int who;
  i64 val;

  bool operator<(const Z& other) const {
    return val < other.val;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N, L;
  cin >> N >> L;
  vector V(N, vector<i64>(L + 1));
  for (int i = 0; i < N; ++i) {
    for (int j = 1; j <= L; ++j) {
      cin >> V[i][j];
    }
  }
  vector sum(N, vector<i64>(L + 1));
  for (int i = 0; i < N; ++i) {
    for (int j = 1; j <= L; ++j) {
      sum[i][j] = sum[i][j - 1] + N * V[i][j];
    }
  }
  vector<int> A, P;
  vector<bool> used(N);
  int ptr = 0;
  while (P.size() != N) {
    int lo = ptr, hi = L * N;
    auto check = [&](int x) {
      Z res{-1, inf};
      for (int i = 0; i < N; ++i) {
        if (used[i]) {
          continue;
        }
        i64 v = sum[i][min(L, N * (x / N))];
        if (min(L, N * ((ptr + N - 1) / N)) - 1 >= 0) {
          v += sum[i][min(L, N * ((ptr + N - 1) / N)) - 1];
        }
        v += (x - N * (x / N)) * V[i][min(L, N * ((x + N - 1) / N))];
        v += (N * ((ptr + N - 1) / N) - ptr) * V[i][min(L, N * ((ptr + N - 1) / N))];
        if (v >= sum[i][L] / N) {
          res = min(res, {i, v});
        }
      }
      return res;
    };
    int res = -1;
    while (lo <= hi) {
      int mid = (lo + hi) / 2;
      if (check(mid).who != -1) {
        res = mid;
        hi = mid - 1;
      } else {
        lo = mid + 1;
      }
    }
    if (res == -1) {
      cout << -1 << "\n";
      return 0;
    }
    A.push_back(res);
    ptr = res + 1;
    int w = check(res).who;
    used[w] = true;
    P.push_back(w);
  }
  for (int i = 0; i < N - 1; ++i) {
    cout << A[i] << " " << N << "\n";
  }
  for (int i = 0; i < N; ++i) {
    cout << P[i] + 1 << " \n"[i + 1 == N];
  }
  return 0;
}

Compilation message (stderr)

naan.cpp: In function 'int main()':
naan.cpp:46:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   46 |   while (P.size() != N) {
      |          ~~~~~~~~~^~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 24
• Subtask 3: 0 / 71