Submission #651189

#	Time	Username	Problem	Language	Result	Execution time	Memory
651189		tvladm2009	Naan (JOI19_naan)	C++14	100 / 100	427 ms	100984 KiB

naan

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

struct Fraction {
  ll a;
  ll b;

  Fraction(ll a, ll b) : a(a), b(b) {

  }
};

ld getld(Fraction fr) {
  return (ld)fr.a / (ld)fr.b;
}

bool operator < (Fraction First, Fraction Second) {
  return (ld)First.a / (ld)First.b <= (ld)Second.a / (ld)Second.b;
}

Fraction operator + (Fraction First, ll Second) {
  return Fraction(First.a + Second * First.b, First.b);
}

Fraction operator + (ll Second, Fraction First) {
  return Fraction(First.a + Second * First.b, First.b);
}

Fraction operator - (Fraction First, ll Second) {
  return Fraction(First.a - Second * First.b, First.b);
}

Fraction operator - (ll Second, Fraction First) {
  return Fraction(-First.a + Second * First.b, First.b);
}

Fraction operator * (Fraction First, ll Second) {
  return {First.a * Second, First.b};
}

Fraction operator * (ll First, Fraction Second) {
  return {Second.a * First, Second.b};
}

signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  int People, n;
  cin >> People >> n;
  vector<vector<int>> a(People, vector<int>(n));
  vector<vector<Fraction>> splitPoint(People, vector<Fraction>(People, Fraction(0, 1)));

  for (int i = 0; i < People; i++) {
    for (int j = 0; j < n; j++) {
      cin >> a[i][j];
    }
  }

  for (int Person = 0; Person < People; Person++) {
    ll totalSum = 0;
    for (auto& x : a[Person]) {
      totalSum += x;
    }
    int done = 0;
    ll currentSum = 0;
    Fraction fromLast(0, 1);
    for (int j = 0; j < People; j++) {
      Fraction want((j + 1) * totalSum, People);
      while (Fraction(currentSum + a[Person][done], 1) < want) {
        currentSum += a[Person][done++];
        fromLast = Fraction(0, 1);
      }
      Fraction dif = want - currentSum;
      Fraction x(dif.a, dif.b * a[Person][done]);
      splitPoint[Person][j] = done + x;
      fromLast = x;
    }
  }

  vector<bool> valid(People, 1);
  vector<int> guys;

  for (int ch = 0; ch < People; ch++) {
    int sol = -1;
    for (int i = 0; i < People; i++) {
      if (valid[i]) {
        if (sol == -1) {
          sol = i;
        } else {
          if (splitPoint[i][ch] < splitPoint[sol][ch]) {
            sol = i;
          }
        }
      }
    }
    valid[sol] = 0;
    if (ch != People - 1) {
      cout << splitPoint[sol][ch].a << " " << splitPoint[sol][ch].b << "\n";
    }
    guys.push_back(sol);
  }
  for (auto &Guy : guys) {
    cout << Guy + 1 << " ";
  }
  return 0;
}

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