제출 #921766

#제출 시각아이디문제언어결과실행 시간메모리
921766boris_mihovNaan (JOI19_naan)C++17
29 / 100
145 ms12456 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 { __int128 p; __int128 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() { while (std::max(p, q) > 1e9) { p /= 2; p++; q /= 2; } std::cout << (llong)p << ' ' << (llong)q << '\n'; } }; bool taken[MAXN]; Fraction s[MAXN]; llong v[MAXN][MAXN]; Fraction nextSum[MAXN]; Fraction currentSum[MAXN]; std::vector <Fraction> positions; std::vector <int> order; void solve() { Fraction takenTo = 0; for (int pos = 1 ; pos <= l ; ++pos) { Fraction minimum = l + 1; int idx = -1; for (int i = 1 ; i <= n ; ++i) { if (taken[i]) { continue; } nextSum[i] = currentSum[i] + (1 - takenTo) * v[i][pos]; if (s[i] <= nextSum[i]) { Fraction must = pos - 1 + takenTo + (s[i] - currentSum[i]) / v[i][pos]; if (must < minimum) { minimum = must; idx = i; } } } if (idx == -1) { takenTo = 0; for (int i = 1 ; i <= n ; ++i) { currentSum[i] = nextSum[i]; } } else { taken[idx] = true; order.push_back(idx); positions.push_back(minimum); takenTo = minimum - pos + 1; std::fill(currentSum + 1, currentSum + n + 1, 0); pos--; } } positions.pop_back(); } void print() { for (int i = 0 ; i < n - 1 ; ++i) { assert(std::__gcd(positions[i].p, positions[i].q) == 1); positions[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; }

컴파일 시 표준 에러 (stderr) 메시지

naan.cpp: In function 'Fraction operator+(const Fraction&, const Fraction&)':
naan.cpp:32:34: warning: narrowing conversion of '((((__int128)left.Fraction::p) * ((__int128)right.Fraction::q)) + (((__int128)right.Fraction::p) * ((__int128)left.Fraction::q)))' from '__int128' to 'llong' {aka 'long long int'} [-Wnarrowing]
   32 |         return {left.p * right.q + right.p * left.q, left.q * right.q};
      |                 ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
naan.cpp:32:61: warning: narrowing conversion of '(((__int128)left.Fraction::q) * ((__int128)right.Fraction::q))' from '__int128' to 'llong' {aka 'long long int'} [-Wnarrowing]
   32 |         return {left.p * right.q + right.p * left.q, left.q * right.q};
      |                                                      ~~~~~~~^~~~~~~~~
naan.cpp: In function 'Fraction operator-(const Fraction&, const Fraction&)':
naan.cpp:37:34: warning: narrowing conversion of '((((__int128)left.Fraction::p) * ((__int128)right.Fraction::q)) - (((__int128)right.Fraction::p) * ((__int128)left.Fraction::q)))' from '__int128' to 'llong' {aka 'long long int'} [-Wnarrowing]
   37 |         return {left.p * right.q - right.p * left.q, left.q * right.q};
      |                 ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
naan.cpp:37:61: warning: narrowing conversion of '(((__int128)left.Fraction::q) * ((__int128)right.Fraction::q))' from '__int128' to 'llong' {aka 'long long int'} [-Wnarrowing]
   37 |         return {left.p * right.q - right.p * left.q, left.q * right.q};
      |                                                      ~~~~~~~^~~~~~~~~
naan.cpp: In function 'Fraction operator*(const Fraction&, const Fraction&)':
naan.cpp:42:24: warning: narrowing conversion of '(((__int128)left.Fraction::p) * ((__int128)right.Fraction::p))' from '__int128' to 'llong' {aka 'long long int'} [-Wnarrowing]
   42 |         return {left.p * right.p, left.q * right.q};
      |                 ~~~~~~~^~~~~~~~~
naan.cpp:42:42: warning: narrowing conversion of '(((__int128)left.Fraction::q) * ((__int128)right.Fraction::q))' from '__int128' to 'llong' {aka 'long long int'} [-Wnarrowing]
   42 |         return {left.p * right.p, left.q * right.q};
      |                                   ~~~~~~~^~~~~~~~~
naan.cpp: In function 'Fraction operator/(const Fraction&, const Fraction&)':
naan.cpp:47:24: warning: narrowing conversion of '(((__int128)left.Fraction::p) * ((__int128)right.Fraction::q))' from '__int128' to 'llong' {aka 'long long int'} [-Wnarrowing]
   47 |         return {left.p * right.q, left.q * right.p};
      |                 ~~~~~~~^~~~~~~~~
naan.cpp:47:42: warning: narrowing conversion of '(((__int128)left.Fraction::q) * ((__int128)right.Fraction::p))' from '__int128' to 'llong' {aka 'long long int'} [-Wnarrowing]
   47 |         return {left.p * right.q, left.q * right.p};
      |                                   ~~~~~~~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...