Submission #1018356

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018356		vjudge1	Carnival Tickets (IOI20_tickets)	C++17	41 / 100	707 ms	142448 KiB

tickets

#include <bits/stdc++.h>
#include "tickets.h"
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<bool> vb;
typedef vector<vb> vvb;
#define ALL(x) begin(x), end(x)
#define pb push_back
#define mp make_pair
#define printBool(x) cout << ((x) ? "YES\n" : "NO\n")
#define printBoolR(x) {cout << ((x) ? "YES\n" : "NO\n"); return;}
inline ll nxt(){ll x;cin>>x;return x;}
#define fill_i(x) generate(ALL(x), nxt)

long long find_maximum(int k, std::vector<std::vector<int>> x) {
    int n = x.size(), m = x[0].size();


    vector<array<int,3>> numbs;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            numbs.pb({x[i][j], i, j});
        }
    }
    sort(ALL(numbs));

    vvi s(n, vi(m, -1));
    vvi rounds(k);
    vi ctr(n, 0);
    int p1 = 0, p2 = n*m-1;
    vector<vector<array<int, 3>>> biggies(n);
    vector<vector<array<int, 3>>> smalls(n);
    if (k == 1) {
        vector<pair<array<int,3>, array<int,3>>> L;
        for (int i = 0; i < n; i++) {
            ii MIN = {1e9, 1e9}, MAX = {-1,-1};
            for (int j = 0; j < m; j++) {
                MIN = min(MIN, {x[i][j], j});
                MAX = max(MAX, {x[i][j], j});
            }
            L.push_back({{MIN.first, i, MIN.second}, {MAX.first, i, MAX.second}});
        }

        sort(ALL(L), [](const pair<array<int,3>, array<int,3>>& a, const pair<array<int,3>, array<int,3>>&b) {
            return a.first[0] + a.second[0] > b.first[0] + b.second[0];
        });

        for (int i = 0; i < n/2; i++) biggies[L[i].second[1]].pb(L[i].second);
        for (int i = n/2; i < n; i++) smalls[L[i].first[1]].pb(L[i].first);

    } else 
    for (;;) {
        while (p1 < n*m && ctr[numbs[p1][1]] == k) p1++;
        if (p1 == n*m) break;
        smalls[numbs[p1][1]].push_back(numbs[p1]);
        ctr[numbs[p1][1]]++;
        p1++;

        while (ctr[numbs[p2][1]] == k) p2--;
        biggies[numbs[p2][1]].push_back(numbs[p2]);
        ctr[numbs[p2][1]]++;
        p2--;
    }

    vvb didInRound(n, vb(k, false));
    int i = 0, j = 0;
    for (int r = 0; r < n*k/2; r++) {
        while (j == smalls[i].size()) i++, j = 0;
        didInRound[i][r%k] = true;
        rounds[r%k].pb(smalls[i][j][0]);
        s[i][smalls[i][j][2]] = r%k;
        j++;
    }

    for (int i = 0; i < n; i++) {
        int j = 0;
        for (int r = 0; r < k; r++) if (!didInRound[i][r]) {
            rounds[r].pb(biggies[i][j][0]);
            s[i][biggies[i][j][2]] = r;
            j++;
        }
    }


    allocate_tickets(s);
    ll score = 0;
    for (int r = 0; r < k; r++) {
        sort(ALL(rounds[r]));
        int med = rounds[r][n/2];
        for (int i = 0; i < n; i++) score += abs(med - rounds[r][i]);
    }
    return score;
}

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:76:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         while (j == smalls[i].size()) i++, j = 0;
      |                ~~^~~~~~~~~~~~~~~~~~~

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