Submission #302055

#	Time	Username	Problem	Language	Result	Execution time	Memory
302055		joseacaz	Carnival Tickets (IOI20_tickets)	C++17	11 / 100	2 ms	768 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), x.end()

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

ll find_maximum(int k, vector<vi> a) {
	int N = a.size();
	int M = a[0].size();
	vector<vi> answer(N, vi(M, -1));
    vpi nums;
    for(int i = 0; i < N; i++)
        for(int j = 0; j < M; j++)
            nums.pb({a[i][j], i*M+j});
    sort(all(nums));
    auto maxim = nums[nums.size()/2];
    vi small(N), big(N);
    int smallP = 0, bigP = N;
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            if(a[i][j] < maxim.first)
                small[i]++;
            else if(a[i][j] == maxim.first && i*M+j < maxim.second)
                small[i]++;
        }
        big[i] = M - small[i];
        if(small[i] == 0)
            smallP++;
        else if(big[i] == 0)
            bigP--;
    }
    vi aux;
    for(int i = 0; i < N; i++)
        aux.pb(i);
    sort(all(aux), [=](int a, int b) {
            return small[a] < small[b];
        });

    ll ans = 0;
    for(int round = 0; round < k; round++)
    {
        for(int i = smallP; i < N/2; i++)
        {
            answer[aux[i]][round] = round;
            ans -= a[aux[i]][round];
        }
        for(int i = bigP; i < N; i++)
        {
            answer[aux[i]][round] = round;
            ans -= a[aux[i]][round];
        }
        for(int i = N/2; i < bigP; i++)
        {
            answer[aux[i]][M-1 - round] = round;
            ans += a[aux[i]][M-1 - round];
        }
        for(int i = 0; i < smallP; i++)
        {
            answer[aux[i]][M-1 - round] = round;
            ans += a[aux[i]][M-1 - round];
        }
    }
    
    allocate_tickets(answer);
	return ans;
}

• 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