Submission #823320

#	Time	Username	Problem	Language	Result	Execution time	Memory
823320		NothingXD	카니발 티켓 (IOI20_tickets)	C++17	0 / 100	1 ms	212 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;

void debug_out(){cerr<<endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 1500 + 10;
const ll inf = 1e18;
int n, m, k, x[maxn][maxn], val[maxn];
int ptl[maxn], ptr[maxn];

bool cmp(int x, int y){
	return val[x] > val[y];
}

ll find_maximum(int _k, vector<vector<int>> X) {
	n = X.size();
	m = X[0].size();
	k = _k;
	int sum = 0;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			x[i][j] = X[i][j];
			sum += x[i][j];
		}
	}
	int cnt = n*k/2;
	int res = -sum;
	for (int i = 0; i < n; i++){
		ptr[i] = m-1;
		for (int j = m-1; cnt && j >= m-k; j--){
			if (x[i][j] == 0) break;
		//	debug(i, j, x[i][j]);
			val[i]++;
			res += 2;
			cnt--;
		}
	}
	for (int i = 0; i < n; i++){
		while(cnt && val[i] < k){
			assert(x[i][m-val[i]-1] == 0);
			cnt--;
			val[i]++;
		}
	}
	assert(cnt == 0);
	vector<vector<int>> ans(n);
	for (int i = 0; i < n; i++){
		ans[i].resize(m, -1);
	}
	for (int rnd = 0; rnd < k; rnd++){
		vector<int> idx;
		for (int i = 0; i < n; i++){
			idx.push_back(i);
		}
		sort(idx.begin(), idx.end(), cmp);
		for (int i = 0; i < n; i++){
			if (i < n/2){
				ans[idx[i]][ptr[idx[i]]] = rnd;
				val[idx[i]]--;
				ptr[idx[i]]--;
			}
			else{
				ans[idx[i]][ptl[idx[i]]] = rnd;
				ptl[idx[i]]++;
			}
		}
	}
	allocate_tickets(ans);
	return res;
}

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