Submission #581379

#	Time	Username	Problem	Language	Result	Execution time	Memory
581379		MohamedFaresNebili	Carnival Tickets (IOI20_tickets)	C++14	11 / 100	493 ms	604 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++) {
                vector<pi> curr; vector<ll> arr;
                for(int l = 0; l < N; l++) {
                    for(int i = 0; i < M; i++) {
                        if(S[l][i] != -1) continue;
                        curr.pb({A[l][i], {l, i}});
                    }
                }
                bool vis[N]; memset(vis, 0, sizeof vis);
 
                while(arr.size() != N) {
                    ll best = -1, x = -1, y = -1;
                    for(ll l = 0; l < curr.size(); l++) {
                        if(vis[curr[l].ss.ff]) continue;
                        ll calc = 0;
                        for(auto u : arr)
                            calc += abs(u - curr[l].ff);
                        if(calc > best)
                            best = calc, x = curr[l].ss.ff, y = curr[l].ss.ss;
                    }
                    vis[x] = 1; S[x][y] = R; arr.pb(A[x][y]);
                }
                sort(arr.begin(), arr.end());
              	ll md = arr[N / 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:34:34: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |                 while(arr.size() != N) {
      |                       ~~~~~~~~~~~^~~~
tickets.cpp:36:37: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |                     for(ll l = 0; l < curr.size(); l++) {
      |                                   ~~^~~~~~~~~~~~~

• 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