Submission #581293

#	Time	Username	Problem	Language	Result	Execution time	Memory
581293		MohamedFaresNebili	Carnival Tickets (IOI20_tickets)	C++14	11 / 100	2 ms	596 KiB

tickets

#include <bits/stdc++.h>
#include "tickets.h"
#include <ext/pb_ds/assoc_container.hpp>

        using namespace std;
        using namespace __gnu_pbds;

        using ll = long long;
        using pi = pair<ll, pair<ll, ll>>;
        using ii = pair<int, int>;

        #define pb push_back
        #define pp pop_back
        #define ff first
        #define ss second

        typedef tree<int, null_type, less<int>, rb_tree_tag,
            tree_order_statistics_node_update> indexed_set;

        ll find_maximum(int K, vector<vector<int>> A) {
            int N = A.size(), M = A[0].size(); ll res = 0;
            vector<vector<int>> S(N, vector<int> (M, -1));

            for(int R = 0; R < K; R++) {
                deque<pi> curr; vector<ll> arr;
                for(int l = 0; l < N; l++) {
                    int i = 0, j = M - 1;
                    while(S[l][i] != -1) i++;
                    while(S[l][j] != -1) j--;
                    curr.pb({A[l][i], {l, i}}),
                    curr.pb({A[l][j], {l, j}});
                }
                bool vis[N]; memset(vis, 0, sizeof vis);
                sort(curr.begin(), curr.end());

                priority_queue<int> lo;
                priority_queue<int, vector<int>, greater<int>> hi;

                while(arr.size() != N) {
                    while(vis[curr.front().ss.ff])
                        curr.pop_front();
                    while(vis[curr.back().ss.ff])
                        curr.pop_back();

                    ll U = curr.front().ff;
                    ll V = curr.back().ff;

                    if(arr.empty()) {
                        arr.pb(curr.front().ff);
                        vis[curr.front().ss.ff] = 1;
                        S[curr.front().ss.ff][curr.front().ss.ss] = R;
                        curr.pop_front(); lo.push(U);
                        continue;
                    }



                    if(lo.size() > hi.size() + 1) {
                        hi.push(lo.top()); lo.pop();
                    }
                    if(lo.size() + 1 < hi.size()) {
                        lo.push(hi.top()); hi.pop();
                    }

                    ll md = 0;

                    if(lo.size() > hi.size()) md = lo.top();
                    if(lo.size() < hi.size()) md = hi.top();
                    if(lo.size() == hi.size()) md = (lo.top() + hi.top()) / 2;

                    if(abs(U - md) > abs(V - md)) {
                        arr.pb(curr.front().ff);
                        vis[curr.front().ss.ff] = 1;
                        S[curr.front().ss.ff][curr.front().ss.ss] = R;
                        curr.pop_front();
                    }
                    else {
                        arr.pb(curr.back().ff);
                        vis[curr.back().ss.ff] = 1;
                        S[curr.back().ss.ff][curr.back().ss.ss] = R;
                        curr.pop_back();
                        swap(U, V);
                    }
                    if(U <= lo.top()) lo.push(U);
                    else hi.push(U);

                }
                sort(arr.begin(), arr.end());
              	ll md = (arr[N / 2] + arr[N / 2 - 1]) / 2;
                for(auto U : arr)
                    res += abs(U - md);
            }
            allocate_tickets(S);
            return res;
        }

Compilation message (stderr)

tickets.cpp: In function 'll find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:39:34: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 |                 while(arr.size() != N) {
      |                       ~~~~~~~~~~~^~~~

• Subtask 1: 11 / 11
• Subtask 2: 0 / 16
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23
• Subtask 7: 0 / 10