Submission #1129294

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129294		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;


mt19937 rng((long long) (new char));


struct Frac {
    __int128 p;
    __int128 q;

    Frac(__int128 a = 0, __int128 b = 1) : p(a), q(b) {}

    void reduce() {
        __int128 d = __gcd(p, q);
        p /= d;
        q /= d;
    }

    ll getIntValue() {
        return p / q;
    }
};


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


__int128 lcm(__int128 a, __int128 b) {
    return a * b / __gcd(a, b);
}


void myassert(bool cond) {
    if (cond == false) {
        while (true);
    }
}


Frac operator + (Frac a, Frac b) {
    Frac c = {0, 0};
    __int128 d = lcm(a.q, b.q);
    myassert(d >= 0);
    c.p = a.p * (d / a.q) + b.p * (d / b.q);
    c.q = d;
    return c;
}


Frac operator - (Frac a, Frac b) { 
    assert(b <= a);
    Frac c;
    __int128 d = lcm(a.q, b.q);
    myassert(d >= 0);
    c.p = a.p * (d / a.q) - b.p * (d / b.q);
    c.q = d;
    return c;
}


Frac operator * (int x, Frac f) {
    Frac res = {f.p * x, f.q};
    res.reduce();
    return res;
}


Frac operator / (Frac f, int x) {
    Frac res = {f.p, f.q * x};
    res.reduce();
    return res;
}


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));
    pref.assign(n + 1, vector<__int128>(L + 1));
    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];
            pref[i][j] = pref[i][j - 1] + v[i][j];
        }
        v[i][L + 1] = 1;
        need[i] = {sum, n};
        need[i].reduce();
    }
    vector<pair<int, Frac>> sol;
    for (int step = 1; step <= 100; step += 1) {
        vector<int> ord(n);
        iota(all(ord), 1);
        shuffle(all(ord), rng);
        shuffle(all(ord), rng);
        shuffle(all(ord), rng);
        shuffle(all(ord), rng);
        shuffle(all(ord), rng);

        vector<pair<int, Frac>> cur;
        Frac eaten = {0, 1};
        int full = 0;
        bool bad = 0;
        for (auto i : ord) {
            Frac split;
            if (full == L) {
                bad = 1;
                break;
            }
            if (need[i] <= v[i][full + 1] * (Frac(full + 1, 1) - eaten)) {
                split = eaten + (need[i] / v[i][full + 1]);
                split.reduce();
            } else {
                Frac aux = need[i];
                aux = aux - v[i][full + 1] * (Frac(full + 1, 1) - eaten);
                split.reduce();
                assert(Frac(0, 1) <= aux);
                int low = full + 2, high = L, sol = full + 1;
                while (low <= high) {
                    int m = (low + high) / 2;
                    if (Frac(pref[i][m] - pref[i][full + 1], 1) <= aux) {
                        sol = m;
                        low = m + 1;
                    } else {
                        high = m - 1;
                    }
                }
                if (sol > L) {
                    bad = 1;
                    break;
                }
                aux = aux - Frac(pref[i][sol] - pref[i][full + 1], 1);
                split = sol + (aux / v[i][sol + 1]);
                split.reduce();
                if (!(split <= Frac(L, 1))) {
                    bad = 1;
                    break;
                }
            }
            eaten = split;
            full = eaten.getIntValue();
            cur.push_back({i, eaten});
        }
        if (bad == 0) {
            sol = cur;
            break;
        }
    }
    if (sol.size() != n) {
        cout << -1 << "\n";
        return 0;
    }
    
    for (int i = 0; i < sol.size() - 1; i += 1) {
        int who = sol[i].first;
        Frac split = sol[i].second;
        cout << (ll) split.p << " " << (ll) 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 'int32_t main()':
naan.cpp:99:16: error: no matching function for call to 'std::vector<std::vector<long long int> >::assign(int, std::vector<__int128>)'
   99 |     pref.assign(n + 1, vector<__int128>(L + 1));
      |     ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/vector:67,
                 from /usr/include/c++/11/functional:62,
                 from /usr/include/c++/11/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/11/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:65,
                 from naan.cpp:1:
/usr/include/c++/11/bits/stl_vector.h:768:9: note: candidate: 'template<class _InputIterator, class> void std::vector<_Tp, _Alloc>::assign(_InputIterator, _InputIterator) [with _InputIterator = _InputIterator; <template-parameter-2-2> = <template-parameter-1-2>; _Tp = std::vector<long long int>; _Alloc = std::allocator<std::vector<long long int> >]'
  768 |         assign(_InputIterator __first, _InputIterator __last)
      |         ^~~~~~
/usr/include/c++/11/bits/stl_vector.h:768:9: note:   template argument deduction/substitution failed:
naan.cpp:99:16: note:   deduced conflicting types for parameter '_InputIterator' ('int' and 'std::vector<__int128>')
   99 |     pref.assign(n + 1, vector<__int128>(L + 1));
      |     ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/vector:67,
                 from /usr/include/c++/11/functional:62,
                 from /usr/include/c++/11/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/11/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:65,
                 from naan.cpp:1:
/usr/include/c++/11/bits/stl_vector.h:749:7: note: candidate: 'void std::vector<_Tp, _Alloc>::assign(std::vector<_Tp, _Alloc>::size_type, const value_type&) [with _Tp = std::vector<long long int>; _Alloc = std::allocator<std::vector<long long int> >; std::vector<_Tp, _Alloc>::size_type = long unsigned int; std::vector<_Tp, _Alloc>::value_type = std::vector<long long int>]'
  749 |       assign(size_type __n, const value_type& __val)
      |       ^~~~~~
/usr/include/c++/11/bits/stl_vector.h:749:47: note:   no known conversion for argument 2 from 'std::vector<__int128>' to 'const value_type&' {aka 'const std::vector<long long int>&'}
  749 |       assign(size_type __n, const value_type& __val)
      |                             ~~~~~~~~~~~~~~~~~~^~~~~
/usr/include/c++/11/bits/stl_vector.h:794:7: note: candidate: 'void std::vector<_Tp, _Alloc>::assign(std::initializer_list<_Tp>) [with _Tp = std::vector<long long int>; _Alloc = std::allocator<std::vector<long long int> >]'
  794 |       assign(initializer_list<value_type> __l)
      |       ^~~~~~
/usr/include/c++/11/bits/stl_vector.h:794:7: note:   candidate expects 1 argument, 2 provided