Submission #1265610

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265610		LucaLucaM	Naan (JOI19_naan)	C++20	29 / 100	547 ms	43200 KiB

naan

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <random>
#include <ctime>

using ll = long long;
using i128 = __int128;
#define debug(x) #x << " = " << x << '\n'

#define int ll

struct Fractie {
  int x, y;
  Fractie() {}
  Fractie(int _x, int _y) : x(_x), y(_y) {}
  Fractie(int _x) : x(_x), y(1) {}
  void normMe() {
    int d = std::__gcd(x, y);
    x /= d;
    y /= d;
  }
  Fractie friend norm(const Fractie &other) {
    Fractie f = other;
    f.normMe();
    return f; 
  };
  Fractie operator * (const Fractie &other) const {
    return norm(Fractie(x * other.x, y * other.y));
  };
  Fractie operator + (const Fractie &other) const {
    return norm(Fractie(x * other.y + other.x * y, y * other.y));
  };
  Fractie operator - (const Fractie &other) const {
    return norm(*this + Fractie(-other.x, other.y));
  }
  Fractie operator / (const Fractie &other) const {
    return norm(*this * Fractie(other.y, other.x));
  }
  bool operator < (const Fractie &other) const {
    return x * other.y < y * other.x;
  };
  bool operator == (const Fractie &other) const {
    return x * other.y == y * other.x;
  };
  bool operator > (const Fractie &other) const {
    return x * other.y > y * other.x;
  };
  bool operator <= (const Fractie &other) const {
    return x * other.y <= y * other.x;
  };
  bool operator >= (const Fractie &other) const {
    return x * other.y >= y * other.x;
  };
};

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

  ll _n, _L;
  std::cin >> _n >> _L;
  int n, L;
  n = _n;
  L = _L;
  std::vector<std::vector<int>> a(n, std::vector<int>(L));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < L; j++) {
      ll x;
      std::cin >> x;
      a[i][j] = x;
    }
  }

  std::vector<std::vector<Fractie>> splits(n, std::vector<Fractie>(n));
  
  for (int i = 0; i < n; i++) {
    ll total = 0;
    for (int j = 0; j < L; j++) {
      total += a[i][j];
    }

    ll sum = 0;
    for (int j = 0, p = 0; j < n; j++) {
      while ((sum + a[i][p]) * n <= total * (j + 1)) {
        sum += a[i][p++];
      }
      // ramane total - sum * n de pus
      // a[i][j] * x * n = total * (j + 1) - sum * n 
      // x = (total * (j + 1) - sum * n) / (n * a[i][j])
      Fractie extra(total * (j + 1) - sum * n, n * a[i][p]);
      extra.normMe();
      splits[i][j] = Fractie(p) + extra;
    }
  }
  
  if (std::clock() > CLOCKS_PER_SEC) {
    std::cout << -1;
    return 0;
  }

  for (int i = 0; i < n; i++) {
    for (auto &f : splits[i]) {
      f.normMe();
    }
  }

  std::vector<Fractie> split;
  std::vector<int> order;

  std::vector<int> remaining(n);
  for (int i = 0; i < n; i++) {
    remaining[i] = i;
  }

  split.push_back(Fractie(0, 1));
  for (int i = 0; i < n; i++) {
    std::reverse(splits[i].begin(), splits[i].end());
  }
  while (!remaining.empty()) {
    Fractie mini = Fractie(1e9, 1);
    int where = -1;
    for (int i : remaining) {
      if (splits[i].back() < mini) {
        mini = splits[i].back();
        where = i;
      }
    }

    assert(where != -1);
    split.push_back(splits[where].back());
    order.push_back(where);
    remaining.erase(std::find(remaining.begin(), remaining.end(), where));
    for (int i : remaining) {
      splits[i].pop_back();
    }
  }

  split.erase(split.begin());
  split.pop_back();

  for (auto &f : split) {
    f.normMe();
    assert(1 <= f.y && f.y <= 1e9);
    std::cout << (ll) f.x << ' ' << (ll) f.y << '\n';
  }
  for (int x : order) {
    std::cout << (ll) x + 1 << ' ';
  }
   
  return 0;
}

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