Submission #1239656

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239656		Sir_Ahmed_Imran	카니발 티켓 (IOI20_tickets)	C++17	25 / 100	714 ms	64628 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 1501
#define nl '\n'
#define ff first
#define ss second
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define add insert
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()

int a[MAXN];
int cnt[MAXN][2];
bool vis[MAXN][MAXN];

ll find_maximum(int k, vector<vector<int>> x){
	int n, m, mx, o, t;
	n = x.size();
	m = x[0].size();
	mx = n * k / 2;
	vector<pii> v;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			v.append({x[i][j], i});
	sort(all(v));
	reverse(all(v));
	t = 0;
	ll answer = 0;
	for(auto & [i, j] : v){
		if(cnt[j][1] == n / 2)
			continue;
		a[j]++;
		t++;
		if(t == mx) break;
	}
	for(int i = 0; i < n; i++)
		cnt[i][1] = 0;
	vector<vector<int>> ans = x;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			ans[i][j] = -1;
	vector<int> w[2];
	vector<pair<int, pii>> u;
	vector<int> z;
	for(int i = 0; i < n; i++)
		z.append(i);
	std::random_device rd;
    std::mt19937 g(rd());
    std::shuffle(all(z), g);
	for(auto & i : z){
		for(int r = 0; r < k; r++){
			u.append({cnt[r][0], {r, 0}});
			u.append({cnt[r][1], {r, 1}});
		}
		for(int s = 0; s < k - a[i]; s++){
			w[0].append(s);
			answer -= x[i][s];
		}
		for(int s = m - a[i]; s < m; s++){
			w[1].append(s);
			answer += x[i][s];
		}
		sort(all(u));
		for(auto & r : u){
			if(w[r.ss.ss].empty() || vis[r.ss.ff][i] == 1 || r.ff == n / 2 || ans[i][w[r.ss.ss].back()] >= 0)
				continue;
			ans[i][w[r.ss.ss].back()] = r.ss.ff;
			cnt[r.ss.ff][r.ss.ss]++;
			vis[r.ss.ff][i] = 1;
			w[r.ss.ss].pop_back();
		}
		w[0].clear();
		w[1].clear();
		u.clear();
	}
	allocate_tickets(ans);
	return answer;
}

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