Submission #832534

#	Time	Username	Problem	Language	Result	Execution time	Memory
832534		gesgha	Carnival Tickets (IOI20_tickets)	C++17	0 / 100	3 ms	724 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
 
#define fr(i, a, b) for(int i = a; i <= b; i++)
#define rf(i, a, b) for(int i = a; i >= b; i--)
#define fe(x, y) for (auto& x : y)
 
#define fi first
#define se second
#define pb push_back
 
#define all(x) x.begin(), x.end()
#define pw(x) (1LL << (x))
#define sz(x) (int)x.size()
 
using namespace std;
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define fbo find_by_order
#define ook order_of_key
template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
template <typename T>
using ve = vector <T>;
 
template <typename T>
bool umx (T& a, T b) { return a < b ? a = b, 1 : 0; }
 
template <typename T>
bool umn (T& a, T b) { return a > b ? a = b, 1 : 0; }
 
using ll = long long;
using ld = long double;
using pll = pair <ll, ll>;
using pii = pair <int, int>;
using ull = unsigned long long;
 
const int oo = 1e9;
const ll OO = 1e18;
const int N = 1e6 + 10;
const int M = 3e3 + 100;
const int mod = 1e9 + 7;

ll dp[M][M];
int p[M][M];

int cnt[M][2];
ve <int> ones[M];
ve <int> zero[M];

long long find_maximum(int k, std::vector<std::vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	ve <ve <int>> R(n);
	for (int i = 0; i < n; i++) {
		int mn = oo, mx = 0;
		for (int j = 0; j < m; j++) {
			cnt[i][x[i][j]]++;
			if (x[i][j]) ones[i].pb(j);
			else zero[i].pb(j);
		}
	}
	set <pair <int, int>> ST;
	for (int i = 0; i < n; i++) ST.insert({cnt[i][1], i});

	ve <int> used(n, 0);
	int ans = 0;
	std::vector<std::vector<int>> answer;
	for (int i = 0; i < n; i++) {
		std::vector<int> row(m);
		for (int j = 0; j < m; j++) row[j] = -1;	
		answer.push_back(row);
	}
	for (int i = 0; i < k; i++) {
		while (sz(ST) && ST.begin() -> fi == 0) ST.erase(ST.begin());
		if(!sz(ST)) break;
		int cnt = min(n / 2, sz(ST));
		ve <pii> nw;
		auto it = ST.end();
		ans += cnt;
		for (int i = 0; i < cnt; i++) {
			--it;
			nw.pb({(it -> fi) - 1, it -> se});
		}
		for (int i = 0; i < cnt; i++) ST.erase(--ST.end());
		for (int i = 0; i < sz(nw); i++) {
			used[nw[i].se]++;
			answer[nw[i].se][ones[nw[i].se].back()] = used[nw[i].se] - 1;
			ones[nw[i].se].pop_back();
			ST.insert(nw[i]);
		}
		// fe(x, nw) cout << x.se << ' ';
		// cout << "\n";
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if(used[i] == k) break;
			if (x[i][j] == 0) {
				answer[i][j] = used[i]++;
			}
		}
		for (int j = 0; j < m; j++) {
			if (used[i] == k) break;
			if (x[i][j] == 1 && answer[i][j] == -1) {
				answer[i][j] = used[i]++;
				ans--;
			}
		}
	}
	allocate_tickets(answer);
	return ans;
}

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:58:7: warning: unused variable 'mn' [-Wunused-variable]
   58 |   int mn = oo, mx = 0;
      |       ^~
tickets.cpp:58:16: warning: unused variable 'mx' [-Wunused-variable]
   58 |   int mn = oo, mx = 0;
      |                ^~

• 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