Submission #1073606

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073606		LCJLY	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	1070 ms	241580 KiB

tickets

#include <bits/stdc++.h>
#include "tickets.h"
//#include "grader.cpp"
using namespace std;
 
#define int long long
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<long long,long long>pii;
typedef pair<long long,pii>pi2;
 
//allocate_tickets(vector<vector<int>>)
 
long long find_maximum(int32_t k, vector<vector<int32_t>>arr){
	int n=arr.size();
	int m=arr[0].size();
	vector<pi2>v;
	int ptr[n];
	for(int x=0;x<n;x++){
		for(int y=0;y<k;y++){
			v.push_back({arr[x][y]+arr[x][m-k+y],{x,y}});
		}
		ptr[x]=m-1;
	}
	sort(v.begin(),v.end());
	reverse(v.begin(),v.end());
	for(int x=0;x<n*k/2;x++){
		ptr[v[x].second.first]--;
	}
	
	{
		vector<pi2>v;
		for(int x=0;x<n;x++){
			for(int y=m-1;y>ptr[x];y--){
				v.push_back({arr[x][y],{x,y}});
			}
			for(int y=0;y<k-(m-1-ptr[x]);y++){
				v.push_back({arr[x][y],{x,y}});
			}			
		}
		
		sort(v.begin(),v.end());
		int counter=0;
		for(int x=0;x<k*n/2;x++){
			counter+=abs(v[x].first-v[k*n-1-x].first);
		}
		int cnt[n+5];
		memset(cnt,0,sizeof(cnt));
		vector<pi2>storage[n+5];
		vector<pi2>storage2[n+5];
		for(int x=0;x<k*n/2;x++){
			cnt[v[x].second.first]++;
			storage[v[x].second.first].push_back(v[x]);
			storage2[v[x+k*n/2].second.first].push_back(v[x+k*n/2]);
		}
	 
		priority_queue<pii>pq;
		for(int x=0;x<n;x++){
			pq.push({cnt[x],x});
		}
		
		vector<vector<int32_t>>ans;
		ans.resize(n);
		for(int x=0;x<n;x++) ans[x]=vector<int32_t>(m,-1);
		
		for(int x=0;x<k;x++){
			bool take[n+5];
			memset(take,0,sizeof(take));
			vector<pii>temp;
			for(int y=0;y<n/2;y++){
				pii cur=pq.top();
				pq.pop();
				take[cur.second]=true;
				cur.first--;
				temp.push_back(cur);
				pi2 take=storage[cur.second].back();
				storage[cur.second].pop_back();
				ans[take.second.first][take.second.second]=x;
			}
			for(int y=0;y<n;y++){
				if(take[y]) continue;
				pi2 take=storage2[y].back();
				storage2[y].pop_back();
				ans[take.second.first][take.second.second]=x;
			}
			for(auto it:temp) pq.push(it);
		}
		allocate_tickets(ans);
		return counter;
	}
}

• 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