Submission #1265569

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265569		LucaLucaM	Naan (JOI19_naan)	C++20	5 / 100	1 ms	328 KiB

naan

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

using ll = long long;
#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 norm() {
    int d = std::__gcd(x, y);
    x /= d;
    y /= d;
  }
  Fractie operator * (const Fractie &other) const {
    return Fractie(x * other.x, y * other.y);
  };
  Fractie operator + (const Fractie &other) const {
    return Fractie(x * other.y + other.x * y, y * other.y);
  };
  Fractie operator - (const Fractie &other) const {
    return *this + Fractie(-other.x, other.y);
  }
  Fractie operator / (const Fractie &other) const {
    return *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);

  int n, L;
  std::cin >> n >> 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++) {
      std::cin >> a[i][j];
    }
  }

  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;
    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];
      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.norm();
    }
  }

  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));
  while (!remaining.empty()) {
    Fractie mini = Fractie(1e9, 1);
    int where = -1;
    for (int i : remaining) {
      while (!splits[i].empty() && splits[i][0] <= split.back()) {
        splits[i].erase(splits[i].begin());
      }
      assert(!splits[i].empty());
      if (splits[i][0] < mini) {
        mini = splits[i][0];
        where = i;
      }
    }

    split.push_back(splits[where][0]);
    order.push_back(where);
    remaining.erase(std::find(remaining.begin(), remaining.end(), where));
  }

  split.erase(split.begin());
  split.pop_back();
  
  for (auto f : split) {
    std::cout << f.x << ' ' << f.y << '\n';
  }
  for (int x : order) {
    std::cout << x + 1 << ' ';
  }
  
  
  return 0;
}

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