Submission #218078

#	Time	Username	Problem	Language	Result	Execution time	Memory
218078		rama_pang	Naan (JOI19_naan)	C++14	100 / 100	1092 ms	102648 KiB

naan

#include <bits/stdc++.h>
using namespace std;
using lint = long long;

lint gcd(lint x, lint y) {
  return min(x, y) == 0 ? max(x, y) :  gcd(y, x % y);
}

lint lcm(lint x, lint y) {
  return (x / gcd(x, y)) * y;
}

struct Rational { // rational number of x/y 
  lint x, y;

  Rational(lint x = 0, lint y = 1) {
    lint g = gcd(x, y);
    x /= g;
    y /= g;

    this->x = x;
    this->y = y;
  }

  Rational operator + (const Rational &o) const {
    Rational a = *this, b = o;
    Rational res;
    lint c = a.x / a.y + b.x / b.y;

    a.x %= a.y;
    b.x %= b.y;

    res.y = lcm(a.y, b.y);
    res.x = (a.x * (res.y / a.y)) + (b.x * (res.y / b.y)) + (c * res.y);

    return res;
  }

  bool operator < (const Rational &o) const {
    if ((x / y) < (o.x / o.y)) return true;
    if ((x / y) > (o.x / o.y)) return false;
    return (x % y) * o.y < (o.x % o.y) * y;
  }

};

int N, L;
vector<vector<int>> V;

vector<lint> sum;
vector<vector<Rational>> split;

vector<Rational> X;
vector<int> P;

void Read() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  cin >> N >> L;
  V.assign(N, vector<int>(L));

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < L; j++) {
      cin >> V[i][j];
    }
  }
}

void Write() {
  for (int i = 0; i + 1 < N; i++) {
    cout << X[i].x << " " << X[i].y << "\n";
  }
  for (int i = 0; i < N; i++) {
    cout << P[i] << " \n"[i == N - 1];
  }
}

void Solve() {
  split.resize(N);
  sum.resize(N);

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < L; j++) {
      sum[i] += V[i][j];
    }
  }

  for (int i = 0; i < N; i++) {
    lint current = 0;
    int p = 0;
    for (int j = 1; j <= N - 1; j++) {
      while ((current + V[i][p]) * N <= sum[i] * j) {
        current += V[i][p++];
      }
      lint rest = sum[i] * j - current * N;
      split[i].emplace_back((Rational(p) + Rational(rest, N * V[i][p])));
    }
  }

  vector<bool> taken(N, false);
  for (int c = 0; c < N; c++) {
    int minim = -1;
    for (int i = 0; i < N; i++) {
      if (taken[i]) continue;
      if (minim == -1 || split[i][c] < split[minim][c]) {
        minim = i;
      }
    }

    taken[minim] = true;
    P.emplace_back(minim + 1);
    if (c + 1 < N) {
      X.emplace_back(split[minim][c]);
    }
  }
}

int main() {
  Read();
  Solve();
  Write();
  return 0;
}

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