제출 #832565

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
832565		gesgha	카니발 티켓 (IOI20_tickets)	C++17	0 / 100	3 ms	980 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];
set <int> can[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);
		}
		for (int j = 0; j < k; j++) can[i].insert(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 j = 0; j < sz(nw); j++) {
			used[nw[j].se]++;
			answer[nw[j].se][ones[nw[j].se].back()] = i;
			can[nw[j].se].erase(i);
			ones[nw[j].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 (!sz(can[i])) break;
			if (x[i][j] == 0) {
				answer[i][j] = *can[i].begin();
				can[i].erase(can[i].begin());
			}
		}
		for (int j = 0; j < m; j++) {
			if (!sz(can[i])) break;
			if (x[i][j] == 1 && answer[i][j] == -1) {
				answer[i][j] = *can[i].begin();
				can[i].erase(can[i].begin());
				ans--;
			}
		}
	}
	allocate_tickets(answer);
	return ans;
}

컴파일 시 표준 에러 (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