Submission #1265589

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265589		LucaLucaM	Naan (JOI19_naan)	C++20	29 / 100	4094 ms	48552 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);
  
  for (int i = 0; i < n; i++) {
    Fractie need(0, 1);
    for (int j = 0; j < L; j++) {
      need = need + a[i][j];
    }
    need = need / n;
    need.normMe();
    int complete = 0;
    Fractie partial = 0;
    for (int _  = 0; _ < n; _++) {
      if (partial == 1) {
        partial = 0;
        complete++;
      }
      Fractie me = (Fractie(1, 1) - partial) * a[i][complete];
      me.normMe();
      if (me >= need) {
        // x * a[i][j] = need
        Fractie x = need / a[i][complete];
        partial = partial + x;
        splits[i].push_back(partial + complete);
        continue;
      }
      partial = 0;
      while (me < need) {
        me = me + a[i][++complete];
      }
      me = me - a[i][complete];
      // me + x * a[i][complete] == need
      Fractie x = (need - me) / a[i][complete];
      partial = x;
      splits[i].push_back(partial + complete);
    }
  }

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

  assert(CLOCKS_PER_SEC == 1'000'000);
  assert(std::clock() < 4 * CLOCKS_PER_SEC);
  
  split.push_back(Fractie(0, 1));
  while (!remaining.empty()) {
    Fractie mini = Fractie(1e9, 1);
    int where = -1;
    for (int i : remaining) {
      if (splits[i][0] < mini) {
        mini = splits[i][0];
        where = i;
      }
    }

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

  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