Submission #1071417

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071417		Ignut	Carnival Tickets (IOI20_tickets)	C++17	27 / 100	448 ms	73296 KiB

tickets

// Ignut

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int INF = 1e9 + 123;

void allocate_tickets(vector<vector<int>> s);

ll find_maximum(int k, vector<vector<int>> x) {
    int n = x.size(), m = x.front().size();

    vector<int> mn, mx;
    for (int i = 0; i < n; i ++) {
        mn.push_back(INF), mx.push_back(-INF);
        for (int j = 0; j < m; j ++) {
            mn.back() = min(mn.back(), x[i][j]);
            mx.back() = max(mx.back(), x[i][j]);
        }    
    }

    vector<int> vals;
    for (int i = 0; i < n; i ++) vals.push_back(mn[i]), vals.push_back(mx[i]);

    sort(vals.begin(), vals.end());
    ll res = -INF;
    int bestVal = -1;
    vector<int> target;
    for (int val : vals) {
        vector<int> vec;
        ll sum = 0;
        int cntL = 0;
        vector<int> currTarget(n);
        vector<pair<int, int>> changeL, changeR;
        for (int i = 0; i < n; i ++) {
            int v_min = abs(val - mn[i]);
            int v_max = abs(val - mx[i]);
            if (mx[i] < val) {
                sum += v_min;
                cntL ++;
                currTarget[i] = mn[i];
                continue;
            }
            if (mn[i] > val) {
                sum += v_max;
                currTarget[i] = mx[i];
                continue;
            }

            if (v_min >= v_max) {
                sum += v_min;
                cntL ++;
                currTarget[i] = mn[i];
                changeL.push_back({v_max - v_min, i});
            }
            else {
                sum += v_max;
                currTarget[i] = mx[i];
                changeR.push_back({v_min - v_max, i});
            }
        }
        sort(changeL.begin(), changeL.end());
        sort(changeR.begin(), changeR.end());

        if (cntL <= n / 2) {
            if (changeR.size() + cntL < n / 2)
                continue;
            while (cntL < n / 2) {
                sum += changeR.back().first;
                int i = changeR.back().second;
                currTarget[i] = mn[i] + mx[i] - currTarget[i];
                changeR.pop_back();
                cntL ++;
            }
        }
        else {
            if (cntL - changeL.size() > n / 2)
                continue;
            while (cntL > n / 2) {
                sum += changeL.back().first;
                int i = changeL.back().second;
                currTarget[i] = mn[i] + mx[i] - currTarget[i];
                changeL.pop_back();
                cntL --;
            }
        }

        // cerr << "try : " << sum << '\n';
        if (sum > res) {
            res = sum;
            bestVal = val;
            target = currTarget;
        }
    }

    vector<vector<int>> s;
    for (int i = 0; i < n; i ++) {
        s.push_back({});
        s.back().assign(m, -1);
        for (int j = 0; j < m; j ++) {
            if (x[i][j] == target[i]) {
                s.back()[j] = 0;
                break;
            }
        }
    }

    allocate_tickets(s);

    return res;
}

Compilation message (stderr)

tickets.cpp: In function 'll find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:68:39: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   68 |             if (changeR.size() + cntL < n / 2)
      |                 ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~
tickets.cpp:79:39: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   79 |             if (cntL - changeL.size() > n / 2)
      |                 ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~
tickets.cpp:29:9: warning: variable 'bestVal' set but not used [-Wunused-but-set-variable]
   29 |     int bestVal = -1;
      |         ^~~~~~~

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