Submission #921796

#TimeUsernameProblemLanguageResultExecution timeMemory
921796boris_mihovNaan (JOI19_naan)C++17
29 / 100
1858 ms56308 KiB
#include <algorithm> #include <iostream> #include <numeric> #include <cassert> #include <vector> typedef long long llong; const int MAXN = 2000 + 10; const int INF = 1e9; int n, l; struct Fraction { llong p; llong q; Fraction() { p = 0; q = 1; } Fraction(llong _p, llong _q = 1) { p = _p; q = _q; llong g = std::__gcd(p, q); p /= g; q /= g; } friend Fraction operator + (const Fraction &left, const Fraction &right) { return {left.p * right.q + right.p * left.q, left.q * right.q}; } friend Fraction operator - (const Fraction &left, const Fraction &right) { return {left.p * right.q - right.p * left.q, left.q * right.q}; } friend Fraction operator * (const Fraction &left, const Fraction &right) { return {left.p * right.p, left.q * right.q}; } friend Fraction operator / (const Fraction &left, const Fraction &right) { return {left.p * right.q, left.q * right.p}; } friend void operator += (Fraction &left, const Fraction &right) { left = left + right; } friend void operator -= (Fraction &left, const Fraction &right) { left = left - right; } friend void operator *= (Fraction &left, const Fraction &right) { left = left * right; } friend void operator /= (Fraction &left, const Fraction &right) { left = left / right; } friend bool operator < (const Fraction &left, const Fraction &right) { return (left.p * right.q < right.p * left.q); } friend bool operator <= (const Fraction &left, const Fraction &right) { return (left.p * right.q <= right.p * left.q); } void print() { std::cout << (llong)p << ' ' << (llong)q << '\n'; } }; bool taken[MAXN]; Fraction s[MAXN]; llong v[MAXN][MAXN]; std::vector <Fraction> positions[MAXN]; std::vector <Fraction> answer; std::vector <int> order; void solve() { for (int i = 1 ; i <= n ; ++i) { Fraction takenTo = 0; Fraction nextSum = 0; Fraction currentSum = 0; for (int pos = 1 ; pos <= l && positions[i].size() < n ; ++pos) { nextSum = currentSum + (1 - takenTo) * v[i][pos]; if (s[i] <= nextSum) { Fraction breakAt = pos - 1 + takenTo + (s[i] - currentSum) / v[i][pos]; positions[i].push_back(breakAt); takenTo = breakAt - pos + 1; currentSum = 0; pos--; } else { currentSum = nextSum; takenTo = 0; } } } for (int i = 0 ; i < n ; ++i) { int minIdx = -1; for (int j = 1 ; j <= n ; ++j) { if (taken[j]) { continue; } if (minIdx == -1 || positions[j][i] < positions[minIdx][i]) { minIdx = j; } } answer.push_back(positions[minIdx][i]); order.push_back(minIdx); taken[minIdx] = true; } } void print() { for (int i = 0 ; i < n - 1 ; ++i) { answer[i].print(); } for (int i = 0 ; i < n ; ++i) { std::cout << order[i] << ' '; } std::cout << '\n'; } void input() { std::cin >> n >> l; for (int i = 1 ; i <= n ; ++i) { for (int j = 1 ; j <= l ; ++j) { std::cin >> v[i][j]; s[i] += v[i][j]; } s[i] /= n; } } void fastIOI() { std::ios_base :: sync_with_stdio(0); std::cout.tie(nullptr); std::cin.tie(nullptr); } int main() { fastIOI(); input(); solve(); print(); return 0; }

Compilation message (stderr)

naan.cpp: In function 'void solve()':
naan.cpp:101:60: warning: comparison of integer expressions of different signedness: 'std::vector<Fraction>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  101 |         for (int pos = 1 ; pos <= l && positions[i].size() < n ; ++pos)
      |                                        ~~~~~~~~~~~~~~~~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...