Submission #895408

#	Time	Username	Problem	Language	Result	Execution time	Memory
895408		MilosMilutinovic	Naan (JOI19_naan)	C++14	29 / 100	30 ms	8024 KiB

naan

#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;
}

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