Submission #1081957

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081957		RaresFelix	Carnival Tickets (IOI20_tickets)	C++17	27 / 100	343 ms	73248 KiB

tickets

#include "tickets.h"
#include <vector>

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using vi = vector<int>;
using ii = pair<int, int>;

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

   // vector<vi> S = x;
   // for(int i = 0; i < n; ++i)
   //     for(int j = 1; j < m; ++j) {
   //         S[i][j] += S[i][j - 1];
   //     }
    vi A(n, 0);
    priority_queue<ii> PQ;
    auto calc = [&](int lin, int a) {
        return x[lin].end()[-a - 1] + x[lin][k - a - 1];
    };

    for(int i = 0; i < n; ++i) {
        PQ.push({calc(i, A[i]), i});
    }
    
    ll sum = 0;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < k; ++j)
            sum -= x[i][j];
    }

    for(int i = 0; i < n * k / 2; ++i) {
        auto [val, id] = PQ.top();
        PQ.pop();
        sum += val;
        ++A[id];
        if(A[id] < k) PQ.push({calc(i, A[i]), i});
    }

    vector<vi> Re(n, vi(m, -1));
    vector<vi> Poz(n), Neg(n);
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < k - A[i]; ++j) Neg[i].push_back(j);
        for(int j = 0; j < A[i]; ++j) Poz[i].push_back(m - 1 - j);
    }

    for(int nr = 0; nr < k; ++nr) {
        vi ord(n);
        iota(ord.begin(), ord.end(), 0);
        sort(ord.begin(), ord.end(), [&](auto a, auto b) {
            return abs((int)Poz[a].size() - (int)Neg[a].size()) >
                    abs((int)Poz[b].size() - (int)Neg[b].size());
        });
        int nr_plus = n / 2, nr_minus = n / 2;

        auto assign = [&](int lin, int sgn) {
            int u;
            if(sgn == 1) {
                u = Poz[lin].back();
                Poz[lin].pop_back();
                --nr_plus;
            } else {
                u = Neg[lin].back();
                Neg[lin].pop_back();
                --nr_minus;
            }
            Re[lin][u] = nr;
        };
        
        for(auto it : ord) {
            if(!nr_plus) {
                assign(it, -1);
            } else if(!nr_minus) {
                assign(it, 1);
            } else {
                if(Poz[it].size() > Neg[it].size()) assign(it, 1);
                else assign(it, -1);
            }
        }
    }

    allocate_tickets(Re);

    return sum;
}

• 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