Submission #1203843

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203843		nikolashami	Carnival Tickets (IOI20_tickets)	C++20	100 / 100	523 ms	54440 KiB

tickets

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

/*void allocate_tickets(vector<vector<int>>a){
	ll n=a.size();
	for(int i=0;i<n;++i){
		for(auto&x:a[i])cout<<x<<' ';
		cout<<'\n';
	}
}*/

#include"tickets.h"

ll find_maximum(int k,vector<vector<int>>x){
	ll n=x.size(),m=x[0].size();
	vector<vector<int>>ret(n);
	for(int i=0;i<n;++i)ret[i].resize(m,-1);
	ll ans=0;
	for(int i=0;i<n;++i){
		for(int j=0;j<k;++j)
			ans-=x[i][j];
	}
	vector<ll>y(n,0);
	priority_queue<array<ll,2>>pq;
	for(int i=0;i<n;++i)
		pq.push({x[i][k-1]+x[i][m-1],i});
	for(int _=0;_<k*(n/2);++_){
		auto[u,v]=pq.top();pq.pop();
		ans+=u,++y[v];
		if(y[v]<k)pq.push({x[v][k-1-y[v]]+x[v][m-y[v]-1],v});
	}
	vector<array<ll,2>>isk(n);
	for(int i=0;i<n;++i)
		isk[i][0]=k-y[i]-1,isk[i][1]=m-y[i];
	for(int rnd=0;rnd<k;++rnd){
		vector<ll>koji(n,0);
		while(pq.size())pq.pop();
		for(int i=0;i<n;++i)pq.push({-isk[i][1],i});
		for(int _=0;_<n/2;++_)koji[pq.top()[1]]^=1,pq.pop();
		for(int i=0;i<n;++i){
			if(koji[i])ret[i][isk[i][1]++]=rnd;
			else ret[i][isk[i][0]--]=rnd;
		}
	}
	allocate_tickets(ret);
	return ans;
}

/*signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cout<<find_maximum(2,{{0,2,5},{1,1,3}});
}*/

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