Submission #519380

#	Time	Username	Problem	Language	Result	Execution time	Memory
519380		ymm	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	719 ms	114536 KiB

tickets

///
///   Oh? You're approaching me?
///

#include <bits/stdc++.h>
#define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x)
#define LoopR(x,l,r) for(ll x = ll(r)-1; x >= ll(l); --x)
#define Kill(x) exit((cout << (x) << '\n', 0))
typedef long long ll;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
using namespace std;

#include "tickets.h"

const int N = 1510;
vector<vector<int>> ans;
int cnt[N], ccnt[N];
int n, m;

//void allocate_tickets(vector<vector<int>> s){}

//int npl(int _, int i){
//	return n-cnt[i]+ccnt[i];
//}
//int nmi(int _, int i){
//	return _-ccnt[i];
//}

ll find_maximum(int k, vector<vector<int>> x)
{
	n = x.size(); m = x[0].size();
	ans = vector<vector<int>>(n, vector<int>(m, -1));
	vector<pll> vec;
	ll fans = 0;
	Loop(i,0,n){
		Loop(j,0,k) {
			fans -= x[i][j];
			vec.push_back({x[i][j] + x[i][m+j-k], i});
		}
	}
	sort(vec.begin(), vec.end(), greater<pll>());
	Loop(i,0,n*k/2){
		cnt[vec[i].second]++;
		fans += vec[i].first;
	}
	Loop(_,0,k){
		int sum=0;
		vector<bool> tag(n);
		Loop(i,0,n){
			if(cnt[i] == ccnt[i])
				ans[i][_-ccnt[i]] = _, --sum;
			else if(_-ccnt[i] == k-cnt[i])
				ans[i][m-cnt[i]+ccnt[i]] = _, ++sum, ++ccnt[i];
			else
				tag[i] = 1;
		}
		Loop(i,0,n) if(tag[i]){
			if(sum > 0)
				ans[i][_-ccnt[i]] = _, --sum;
			else
				ans[i][m-cnt[i]+ccnt[i]] = _, ++sum, ++ccnt[i];
		}
		assert(sum == 0);
	}
	allocate_tickets(ans);
	return fans;
}

//int main(){
//	cout << find_maximum(1, {{5, 9}, {1, 4}, {3, 6}, {2, 7}}) << '\n';
//	Loop(i,0,n){
//		Loop(j,0,m) cout << ans[i][j] << ' ';
//		cout << '\n';
//	}
//}

• 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