Submission #303310

#	Time	Username	Problem	Language	Result	Execution time	Memory
303310		Utaha	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	1274 ms	84492 KiB

tickets

#include "tickets.h"
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define F first 
#define S second
#define ALL(a) a.begin(),a.end()
#define MP make_pair
#define pb push_back
#define eb emplace_back
#define SZ(a) ((int)a.size())
#define REP(i,n) for(int i=0;i<(n);i++)

const int maxn = 1505;

int n,m,k;
std::vector<std::vector<int>> ans;

vector<int> idx[maxn]; //pos
vector<int> idx2[maxn]; //neg

set<pii> st;
void distribute(){//distrubute all tickets in idx[] to k rounds, each round with n/2 distinct color
	REP(i,n){
		st.insert(MP(SZ(idx[i]),i));
	}

	REP(i,k){
		auto it = prev(st.end());
		vector<int> clr={};
		bool vis[maxn]={0};
		REP(j,n/2){
			clr.pb(it->S);
			--it;
		}
		for(int j:clr){
			vis[j] = 1;
			ans[j][idx[j].back()] = i;
			st.erase(MP(SZ(idx[j]),j));
			idx[j].pop_back();
			st.insert(MP(SZ(idx[j]),j));
		}
		REP(j,n) if(!vis[j]){
			ans[j][idx2[j].back()] = i;
			idx2[j].pop_back();
		}
	}
}

// bool check(vector<int> v){
// 	assert(SZ(v)==n);
// 	sort(ALL(v));
// 	reverse(ALL(v));
// 	int sum = 0;
// 	REP(i,SZ(v)){
// 		sum+=v[i];
// 		if(sum>(i+1) * k) return 0;
// 	}
// 	return 1;
// }

ll val[maxn][maxn];

priority_queue<pll> pq;
int iter[maxn];

long long find_maximum(int _k, std::vector<std::vector<int>> a) {
	n = a.size();
	m = a[0].size();
	k=_k;
	ans.resize(n);
	REP(i,n) ans[i].resize(m);
	REP(i,n) REP(j,m) ans[i][j]=-1;

	ll ret = 0;
	
	REP(i,n){
		REP(j,k) ret -= a[i][j];
		REP(j,k){
			val[i][j] = a[i][m-1-j] + a[i][k-1-j];
		}
	}
	REP(i,n) iter[i] = 0;

	REP(i,n) pq.push(MP(val[i][0],i));

	REP(T,n*k/2){
		auto cur = pq.top();
		pq.pop();
		int idx = cur.S;

		ret += cur.F;

		iter[idx]++;

		if(iter[idx]==k) continue;
		pq.push(MP(val[idx][iter[idx]],idx));
	}

	// REP(i,n) cout<<iter[i]<<" \n"[i==n-1];

	{
		REP(i,n){
			REP(j,k-iter[i])
				idx2[i].pb(j);

			REP(j,iter[i])
				idx[i].pb(m-1-j);
		}
		// REP(i,n) {
			// for(int j:idx[i]) cout<<j<<' ';
			// cout<<'\n';
		// }

		distribute();
	}

	allocate_tickets(ans);
	return ret;
}

• 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