제출 #1073529

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1073529		LCJLY	카니발 티켓 (IOI20_tickets)	C++14	76 / 100	1056 ms	291428 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<m;y++){
			v.push_back({arr[x][y],{x,y}});
		}
		ptr[x]=m-1;
	}
	sort(v.begin(),v.end());
	vector<pi2>lft[n+5];
	vector<pi2>rgt[n+5];
	for(int x=0;x<n*m/2;x++){
		lft[v[x].second.first].push_back(v[x]);
		rgt[v[x+n*m/2].second.first].push_back(v[x+n*m/2]);
	}
	
	vector<pii>v2;
	int l=0;
	for(int x=0;x<n;x++){
		int hold=max(0LL,k-(int)lft[x].size());
		ptr[x]-=hold;
			
		int cur=0;
		for(int y=min((int)k,(int)lft[x].size())-1;y>=0;y--){
			//assert(y<ptr[x]-cur);
			//if(m-1-(ptr[x]-cur)==(int)rgt[x].size()) break;
			if(y>=ptr[x]-cur) break;
			v2.push_back({arr[x][y]+arr[x][ptr[x]-cur],x});
			cur++;
		}
		l+=min((int)k,(int)lft[x].size());
	}
	//show(l,l);
	sort(v2.begin(),v2.end());
	reverse(v2.begin(),v2.end());
	//for(auto it:v2){
		//show2(it.first,it.first,it.second,it.second);
	//}
	int index=0;
	while(l>k*n/2){
		l--;
		ptr[v2[index].second]--;
		index++;
	}
	
	//for(int x=0;x<n;x++){
		//show2(x,x,ptr[x],ptr[x]);
	//}
	
	{
		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: 0 / 14
• Subtask 4: 14 / 14
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23
• Subtask 7: 0 / 10