Submission #895408

# Submission time Handle Problem Language Result Execution time Memory
895408 2023-12-29T22:14:08 Z MilosMilutinovic Naan (JOI19_naan) C++14
29 / 100
30 ms 8024 KB
#include <bits/stdc++.h>

using namespace std;

struct frac {
  long long p, q;
  frac() : p(1), q(0) {}
  frac(long long p, long long q) : p(p), q(q) {}
};

bool operator < (const frac &a, const frac &b) {
  return (__int128) a.p * b.q < (__int128) b.p * a.q;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, l;
  cin >> n >> l;
  vector<vector<int>> v(n, vector<int>(l));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < l; j++) {
      cin >> v[i][j];
    }
  }
  vector<vector<frac>> to(n, vector<frac>(n));
  for (int i = 0; i < n; i++) {
    vector<long long> pref(l);
    for (int j = 0; j < l; j++) {
      if (j > 0) {
        pref[j] = pref[j - 1];
      }
      pref[j] += v[i][j];
    }
    int ptr = 0;
    for (int j = 0; j < n; j++) {
      while (pref[ptr] * 1LL * n < pref[l - 1] * (j + 1)) {
        ptr += 1;
      }
      to[i][j] = frac(pref[l - 1] * (j + 1) - (ptr == 0 ? 0 : pref[ptr - 1]) * n + ptr * n * v[i][ptr], n * v[i][ptr]);
    }
  }
  vector<bool> was(n);
  vector<frac> all;
  vector<int> p;
  for (int i = 0; i < n; i++) {
    vector<int> ids;
    for (int j = 0; j < n; j++) {
      if (!was[j]) {
        ids.push_back(j);
      }
    }
    sort(ids.begin(), ids.end(), [&](int a, int b) {
      return to[a][i] < to[b][i];
    });
    all.push_back(to[ids[0]][i]);
    was[ids[0]] = true;
    p.push_back(ids[0]);
  }
  all.pop_back();
  for (int i = 0; i < (int) all.size(); i++) {
    cout << all[i].p << " " << all[i].q << '\n';
  }
  for (int i = 0; i < n; i++) {
    cout << p[i] + 1 << " ";
  }
  cout << '\n';
  return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 520 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 1 ms 520 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 1 ms 348 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 1 ms 348 KB Output is correct
37 Correct 1 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 1 ms 348 KB Output is correct
40 Correct 1 ms 348 KB Output is correct
41 Correct 1 ms 348 KB Output is correct
42 Correct 1 ms 348 KB Output is correct
43 Incorrect 30 ms 8024 KB Integer parameter [name=A_i] equals to -2024391405, violates the range [1, 2000000000000]
44 Halted 0 ms 0 KB -