Submission #1129320

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129320		antonn	Naan (JOI19_naan)	C++20	Compilation error	0 ms	0 KiB

naan

#include <bits/stdc++.h>


using namespace std;


#define ll long long
#define ld long double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()


int n, L;
vector<vector<int>> v;
vector<vector<ll>> pref;

struct Frac {
    __int128 p;
    __int128 q;

    Frac(ll a = 0, ll b = 1) : p(a), q(b) {}
    
    void reduct() {
        ll d = __gcd(p, q);
        p /= d;
        q /= d;
    }
};


bool operator <= (Frac a, Frac b) {
    return (__int128) a.p * b.q <= (__int128) b.p * a.q;
}


bool operator < (Frac a, Frac b) {
    return (__int128) a.p * b.q <  (__int128) b.p * a.q;
}


Frac operator + (Frac a, Frac b) {
    Frac c;
    c.p = a.p * b.q + b.p * a.q;
    c.q = a.q * b.q;
    return c;
}


Frac operator - (Frac a, Frac b) {
    Frac c;
    c.p = a.p * b.q - b.p * a.q;
    c.q = a.q * b.q;
    return c;
}


Frac operator - (ll x, Frac f) {
    return {x * f.q - f.p, f.q};
}


Frac operator - (Frac f, ll x) {
    return {f.p - x * f.q, f.q};
}


Frac operator * (Frac f, ll x) {
    f.p *= x;
    return f;
}


Frac operator / (Frac f, ll x) {
    f.q *= x;
    return f;
}


int32_t main() {
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    cin >> n >> L;
    v.assign(n + 1, vector<int>(L + 2));
    vector<Frac> need(n + 1);
    for (int i = 1; i <= n; i += 1) {
        ll sum = 0;
        for (int j = 1; j <= L; j += 1) {
            cin >> v[i][j];
            sum += v[i][j];
        }
        v[i][L + 1] = 1;
        need[i] = {sum, n};
    }
    vector<vector<Frac>> cuts(n + 1);
    for (int i = 1; i <= n; i += 1) {
        Frac pos = {0, 1};
        Frac c = {0, 1};
        Frac sum = {0, 1};
        int full = 0;
        cuts[i].push_back({0, 1});
        while (full != L) {
            if (sum + (full + 1 - c) * v[i][full + 1] <= need[i]) {
                sum = sum + (full + 1 - c) * v[i][full + 1];
                full += 1;
                c = {full, 1};
            } else {
                c = c + (need[i] - sum) / v[i][full + 1];
                c.reduct();
                cuts[i].push_back(c);
                assert(c.p != 0);
                sum = {0, 1};
            }
        }
        assert(cuts[i].size() == n);
        cuts[i].push_back({L, 1});
    }
    vector<int> rem(n);
    iota(all(rem), 1);
    vector<pair<int, Frac>> sol;
    Frac last = {-1, 1};
    for (int it = 1; it <= n; it += 1) {
        pair<int, Frac> best = {-1, {L, 1}};
        for (int i : rem) {
            int low = 0, high = n - 1, sol = -1;
            while (low <= high) {
                int mid = (low + high) / 2;
                if (last <= cuts[i][mid]) {
                    sol = mid;
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
            if (sol != -1) {
                if (cuts[i][sol + 1] <= best.second) {
                    assert(i != 0 && sol != -1);
                    best = {i, cuts[i][sol + 1]};
                }
            }
        }
        if (best.first == -1) {
            cout << -1 << "\n";
            return 0;
        }
        sol.push_back(best);
        vector<int> nw;
        for (auto i : rem) {
            if (i != best.first) {
                nw.push_back(i);
            }
        }
        rem = nw;
        last = best.second;
    }
    for (int i = 0; i < sol.size() - 1; i += 1) {
        int who = sol[i].first;
        Frac split = sol[i].second;
        // assert(split.p != 0);
        cout << split.p << " " << split.q << "\n";
    }
    for (int i = 0; i < sol.size(); i += 1) {
        int who = sol[i].first;
        Frac split = sol[i].second;
        cout << who << " ";
    }
    cout << "\n";
    return 0;
}

Compilation message (stderr)

naan.cpp: In function 'Frac operator-(long long int, Frac)':
naan.cpp:58:21: warning: narrowing conversion of '((((__int128)x) * f.Frac::q) - f.Frac::p)' from '__int128' to 'long long int' [-Wnarrowing]
   58 |     return {x * f.q - f.p, f.q};
      |             ~~~~~~~~^~~~~
naan.cpp:58:30: warning: narrowing conversion of 'f.Frac::q' from '__int128' to 'long long int' [-Wnarrowing]
   58 |     return {x * f.q - f.p, f.q};
      |                            ~~^
naan.cpp: In function 'Frac operator-(Frac, long long int)':
naan.cpp:63:17: warning: narrowing conversion of '(f.Frac::p - (((__int128)x) * f.Frac::q))' from '__int128' to 'long long int' [-Wnarrowing]
   63 |     return {f.p - x * f.q, f.q};
      |             ~~~~^~~~~~~~~
naan.cpp:63:30: warning: narrowing conversion of 'f.Frac::q' from '__int128' to 'long long int' [-Wnarrowing]
   63 |     return {f.p - x * f.q, f.q};
      |                            ~~^
naan.cpp: In function 'int32_t main()':
naan.cpp:162:14: error: ambiguous overload for 'operator<<' (operand types are 'std::ostream' {aka 'std::basic_ostream<char>'} and '__int128')
  162 |         cout << split.p << " " << split.q << "\n";
      |         ~~~~ ^~ ~~~~~~~
      |         |             |
      |         |             __int128
      |         std::ostream {aka std::basic_ostream<char>}
In file included from /usr/include/c++/11/istream:39,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from naan.cpp:1:
/usr/include/c++/11/ostream:166:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long int) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]'
  166 |       operator<<(long __n)
      |       ^~~~~~~~
/usr/include/c++/11/ostream:170:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long unsigned int) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]'
  170 |       operator<<(unsigned long __n)
      |       ^~~~~~~~
/usr/include/c++/11/ostream:174:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(bool) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]'
  174 |       operator<<(bool __n)
      |       ^~~~~~~~
In file included from /usr/include/c++/11/ostream:829,
                 from /usr/include/c++/11/istream:39,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from naan.cpp:1:
/usr/include/c++/11/bits/ostream.tcc:91:5: note: candidate: 'std::basic_ostream<_CharT, _Traits>& std::basic_ostream<_CharT, _Traits>::operator<<(short int) [with _CharT = char; _Traits = std::char_traits<char>]'
   91 |     basic_ostream<_CharT, _Traits>::
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/istream:39,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from naan.cpp:1:
/usr/include/c++/11/ostream:181:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(short unsigned int) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]'
  181 |       operator<<(unsigned short __n)
      |       ^~~~~~~~
In file included from /usr/include/c++/11/ostream:829,
                 from /usr/include/c++/11/istream:39,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from naan.cpp:1:
/usr/include/c++/11/bits/ostream.tcc:105:5: note: candidate: 'std::basic_ostream<_CharT, _Traits>& std::basic_ostream<_CharT, _Traits>::operator<<(int) [with _CharT = char; _Traits = std::char_traits<char>]'
  105 |     basic_ostream<_CharT, _Traits>::
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/istream:39,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from naan.cpp:1:
/usr/include/c++/11/ostream:192:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(unsigned int) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]'
  192 |       operator<<(unsigned int __n)
      |       ^~~~~~~~
/usr/include/c++/11/ostream:201:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long long int) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]'
  201 |       operator<<(long long __n)
      |       ^~~~~~~~
/usr/include/c++/11/ostream:205:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long long unsigned int) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]'
  205 |       operator<<(unsigned long long __n)
      |       ^~~~~~~~
/usr/include/c++/11/ostream:220:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(double) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]'
  220 |       operator<<(double __f)
      |       ^~~~~~~~
/usr/include/c++/11/ostream:224:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(float) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]'
  224 |       operator<<(float __f)
      |       ^~~~~~~~
/usr/include/c++/11/ostream:232:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long double) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]'
  232 |       operator<<(long double __f)
      |       ^~~~~~~~
/usr/include/c++/11/ostream:518:5: note: candidate: 'std::basic_ostream<_CharT, _Traits>& std::operator<<(std::basic_ostream<_CharT, _Traits>&, char) [with _CharT = char; _Traits = std::char_traits<char>]'
  518 |     operator<<(basic_ostream<_CharT, _Traits>& __out, char __c)
      |     ^~~~~~~~
/usr/include/c++/11/ostream:524:5: note: candidate: 'std::basic_ostream<char, _Traits>& std::operator<<(std::basic_ostream<char, _Traits>&, char) [with _Traits = std::char_traits<char>]'
  524 |     operator<<(basic_ostream<char, _Traits>& __out, char __c)
      |     ^~~~~~~~
/usr/include/c++/11/ostream:530:5: note: candidate: 'std::basic_ostream<char, _Traits>& std::operator<<(std::basic_ostream<char, _Traits>&, signed char) [with _Traits = std::char_traits<char>]'
  530 |     operator<<(basic_ostream<char, _Traits>& __out, signed char __c)
      |     ^~~~~~~~
/usr/include/c++/11/ostream:535:5: note: candidate: 'std::basic_ostream<char, _Traits>& std::operator<<(std::basic_ostream<char, _Traits>&, unsigned char) [with _Traits = std::char_traits<char>]'
  535 |     operator<<(basic_ostream<char, _Traits>& __out, unsigned char __c)
      |     ^~~~~~~~
/usr/include/c++/11/ostream:544:5: note: candidate: 'std::basic_ostream<char, _Traits>& std::operator<<(std::basic_ostream<char, _Traits>&, wchar_t) [with _Traits = std::char_traits<char>]' (deleted)
  544 |     operator<<(basic_ostream<char, _Traits>&, wchar_t) = delete;
      |     ^~~~~~~~
/usr/include/c++/11/ostream:549:5: note: candidate: 'std::basic_ostream<char, _Traits>& std::operator<<(std::basic_ostream<char, _Traits>&, char8_t) [with _Traits = std::char_traits<char>]' (deleted)
  549 |     operator<<(basic_ostream<char, _Traits>&, char8_t) = delete;
      |     ^~~~~~~~
/usr/include/c++/11/ostream:554:5: note: candidate: 'std::basic_ostream<char, _Traits>& std::operator<<(std::basic_ostream<char, _Traits>&, char16_t) [with _Traits = std::char_traits<char>]' (deleted)
  554 |     operator<<(basic_ostream<char, _Traits>&, char16_t) = delete;
      |     ^~~~~~~~
/usr/include/c++/11/ostream:558:5: note: candidate: 'std::basic_ostream<char, _Traits>& std::operator<<(std::basic_ostream<char, _Traits>&, char32_t) [with _Traits = std::char_traits<char>]' (deleted)
  558 |     operator<<(basic_ostream<char, _Traits>&, char32_t) = delete;
      |     ^~~~~~~~