Submission #929126

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
929126	2024-02-17T18:24:35 Z	EJIC_B_KEDAX	Carnival Tickets (IOI20_tickets)	C++17	Compilation error	0 ms	0 KB

tickets

#include <bits/stdc++.h>
#include "tickets.h"
 
using ll = long long;
 
using namespace std;
 
mt19937_64 mt(time(nullptr));
 
ll find_maximum(int k, vector<vector<int>> t) {
    int n = t.size(), m = t[0].size();
    multiset<pair<int, int>> st;
    vector<vector<int>> cost(n, vector<int>(k + 1, -1));
    vector<int> ptr(n, 0);
    ll res = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k; j++) {
            res -= t[i][j];
            cost[j] = t[i][m - 1 - j] + t[i][k - 1 - j];
        }
    }
    for (int i = 0; i < n; i++) {
        st.emplace(cost[i][0], i);
    }
    for (int _ = 0; _ < n * k / 2; _++) {
        auto [w, i] = *st.begin();
        st.erase(st.begin());
        res += w;
        st.emplace(cost[i][++ptr[i]], i);
    }
    vector<vector<int>> nt(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k - ptr[i]; j++) {
            nt[i].push_back(t[i][j]);
        }
        for (int j = ptr[i] - 1; j >= 0; j--) {
            nt[i].push_back(t[i][m - 1 - j]);
        }
    }
    t = nt;
    m = k;
    vector<int> all;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            all.push_back(t[i][j]);
        }
    }
    sort(all.begin(), all.end());
    int middle = all[all.size() / 2];
    vector<pair<ll, int>> a(n);
    vector<int> bg(n, 0), end(n, m - 1);
    vector<vector<int>> s(n, vector<int>(m, -1));
    for (int i = 0; i < n; i++) {
        a[i].first = 0;
        a[i].second = i;
        for (int j = 0; j < m; j++) {
            t[i][j] -= middle;
        }
    }
    int bgs = 0, ends = 0;
    for (int i = 0; i < n; i++) {
        for (int st = 0; st < k; st++) {
            if ((abs(t[i][bg[i]]) > abs(t[i][end[i]]) && t[i][bg[i]] <= 0) || t[i][end[i]] < 0) {
                bgs++;
                bg[i]++;
            } else {
                ends++;
                end[i]--;
            }
        }
    }
    if (bgs > ends) {
        multiset<pair<int, int>> st;
        for (int i = 0; i < n; i++) {
            for (int j = bg[i] - 1; j >= 0; j--) {
                int sw = end[i] - (bg[i] - j - 1);
                if (t[i][sw] >= 0) {
                    st.emplace(-t[i][j] - t[i][sw], i);
                }
            }
        }
        while (bgs > ends) {
            assert(!st.empty());
            bgs--;
            ends++;
            auto [w, i] = *st.begin();
            st.erase(st.begin());
            bg[i]--;
            end[i]--;
        }
    } else if (ends > bgs) {
        multiset<pair<int, int>> st;
        for (int i = 0; i < n; i++) {
            for (int j = end[i] + 1; j < m; j++) {
                int sw = bg[i] + j - end[i] - 1;
                if (t[i][sw] <= 0) {
                    st.emplace(t[i][j] + t[i][sw], i);
                }
            }
        }
        while (bgs < ends) {
            bgs++;
            ends--;
            auto [w, i] = *st.begin();
            st.erase(st.begin());
            bg[i]++;
            end[i]++;
        }
    }
    vector<int> l(n), r(n);
    for (int i = 0; i < n; i++) {
        l[i] = bg[i];
        r[i] = m - end[i] - 1;
    }
    for (int st = 0; st < k; st++) {
        vector<int> used(n, 0);
        int bal = 0;
        for (int i = 0; i < n; i++) {
            if (l[i] == k - st) {
                used[i] = 1;
                l[i]--;
                s[i][l[i]] = st;
                bal--;
            }
            if (r[i] == k - st) {
                used[i] = 1;
                s[i][m - r[i]] = st;
                r[i]--;
                bal++;
            }
        }
        for (int i = 0; i < n; i++) {
            if (!used[i]) {
                if (bal > 0) {
                    used[i] = 1;
                    l[i]--;
                    s[i][l[i]] = st;
                    bal--;
                } else {
                    used[i] = 1;
                    s[i][m - r[i]] = st;
                    r[i]--;
                    bal++;
                }
            }
        }
    }
    allocate_tickets(s);
    return res;
}

Compilation message

tickets.cpp: In function 'll find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:19:55: error: no match for 'operator=' (operand types are '__gnu_cxx::__alloc_traits<std::allocator<std::vector<int> >, std::vector<int> >::value_type' {aka 'std::vector<int>'} and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'})
   19 |             cost[j] = t[i][m - 1 - j] + t[i][k - 1 - j];
      |                                                       ^
In file included from /usr/include/c++/10/vector:72,
                 from /usr/include/c++/10/functional:62,
                 from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from tickets.cpp:1:
/usr/include/c++/10/bits/vector.tcc:198:5: note: candidate: 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(const std::vector<_Tp, _Alloc>&) [with _Tp = int; _Alloc = std::allocator<int>]'
  198 |     vector<_Tp, _Alloc>::
      |     ^~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/vector.tcc:199:42: note:   no known conversion for argument 1 from '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} to 'const std::vector<int>&'
  199 |     operator=(const vector<_Tp, _Alloc>& __x)
      |               ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
In file included from /usr/include/c++/10/vector:67,
                 from /usr/include/c++/10/functional:62,
                 from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from tickets.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:709:7: note: candidate: 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(std::vector<_Tp, _Alloc>&&) [with _Tp = int; _Alloc = std::allocator<int>]'
  709 |       operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:709:26: note:   no known conversion for argument 1 from '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} to 'std::vector<int>&&'
  709 |       operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
      |                 ~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_vector.h:730:7: note: candidate: 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(std::initializer_list<_Tp>) [with _Tp = int; _Alloc = std::allocator<int>]'
  730 |       operator=(initializer_list<value_type> __l)
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:730:46: note:   no known conversion for argument 1 from '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} to 'std::initializer_list<int>'
  730 |       operator=(initializer_list<value_type> __l)
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~