Submission #1151347

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151347		abczz	Naan (JOI19_naan)	C++20	100 / 100	917 ms	96036 KiB

naan

#include <iostream>
#include <numeric>
#include <vector>
#define ll long long

using namespace std;

vector <ll> V;
ll n, l, A[2000][2000], S[2000];
bool B[2000];

struct Frac{
  ll a;
  ll b;
};
vector <Frac> X[2000];
Frac simplify(Frac A) {
  ll x = gcd(A.a, A.b);
  return {A.a/x, A.b/x};
}
Frac operator+(Frac A, Frac B) {
  return simplify({A.a*B.b+A.b*B.a, A.b*B.b});
}
Frac operator-(Frac A, Frac B) {
  return simplify({A.a*B.b-A.b*B.a, A.b*B.b});
}
Frac operator*(Frac A, Frac B) {
  return simplify({A.a*B.a, A.b*B.b});
}
Frac operator/(Frac A, Frac B) {
  return simplify({A.a*B.b, A.b*B.a});
}
bool lt(Frac A, Frac B) {
  __int128 u = A.a;
  u *= (__int128)B.b;
  __int128 v = A.b;
  v *= (__int128)B.a;
  return u < v;
}
void print(Frac A) {
  cout << A.a << " " << A.b << '\n';
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cin >> n >> l;
  for (int i=0; i<n; ++i) {
    for (int j=0; j<l; ++j) {
      cin >> A[i][j];
      S[i] += A[i][j];
    }
    ll x = 1, s = 0;
    for (int j=0; j<l; ++j) {
      while (x < n) {
        if (s*n <= S[i]*x && S[i]*x <= (s+A[i][j])*n) {
          X[i].push_back(Frac{j, 1} + simplify(Frac({S[i]*x-s*n, A[i][j]*n})));
          ++x;
        }
        else break;
      }
      s += A[i][j];
    }
  }
  for (int x=0; x<n-1; ++x) {
    Frac tmp = {l, 1};
    ll id = -1;
    for (int i=0; i<n; ++i) {
      if (B[i]) continue;
      if (lt(X[i][x], tmp)) {
        tmp = X[i][x];
        id = i;
      }
    }
    print(X[id][x]);
    V.push_back(id+1);
    B[id] = 1;
  }
  for (auto u : V) {
    cout << u << " ";
  }
  for (int i=0; i<n; ++i) {
    if (!B[i]) cout << i+1 << " ";
  }
  cout << '\n';
}

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