Submission #794904

#	Time	Username	Problem	Language	Result	Execution time	Memory
794904		vjudge1	Carnival Tickets (IOI20_tickets)	C++17	0 / 100	1 ms	596 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
long long best[1501], ans;
vector<pair<long long, long long>> x2[1501], arr;
vector<int> zeros[1501], ones[1501];
int one_cnt[1501];
void calc(vector<int> v) {
    sort(v.begin(), v.end());
    for(auto i: v)
        ans+=abs(i-v[v.size()/2]);
}
long long find_maximum(int k, vector<vector<int>> x) {
	long long n = x.size();
	long long m = x[0].size();
	vector<vector<int>> answer(n,vector<int>(m,-1));
    for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (!x[i][j])
				zeros[i].push_back(j);
			else 
                ones[i].push_back(j), one_cnt[i]++;
    for(int i = 0; i < k; i++) {
        vector<pair<int, int>> arr;
        for(int j = 0; j < n; j++)
            arr.push_back({one_cnt[j], j});
        sort(arr.begin(), arr.end());
        int one = 0, zero = 0;
        for(int j = 0; j < n; j++) {
            if(one_cnt[j]) one++;
            if(one_cnt[j]!=m-i) zero++; 
        }
        int noz=n/2,noo=n/2;
        if(one<n/2)
            noo=one,noz=n-noo;
        if(zero<n/2)
            noz=zero,noo=n-noz;
        vector<int> val;
        for (int j = 0; j < zero; j++) {
			val.push_back(0);
			int color = arr[j].second;
            vector<int> x = zeros[color];
			answer[color][x.back()] = i;
			zeros[color].pop_back();
		}
		for (int j = 0; j < one; j++) {
			val.push_back(1);
			int color = arr[n - j - 1].second;
			answer[color][ones[color].back()] = i;
			ones[color].pop_back();
			one_cnt[color]--;
		}
        calc(val);
    }
	allocate_tickets(answer);
	return ans;
}

• Subtask 1: 0 / 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