Submission #353686

#	Time	Username	Problem	Language	Result	Execution time	Memory
353686		amunduzbaev	Carnival Tickets (IOI20_tickets)	C++14	0 / 100	661 ms	65644 KiB

tickets

#include "tickets.h"

#ifndef EVAL
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
using namespace std;
 
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define fastios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define vll vector<ll>
#define vii vector<int>
#define vpii vector<pii>
#define vpll vector<pll>
#define cnt(a)__builtin_popcount(a)
template<class T> bool umin(T& a, const T& b) {return a > b? a = b, true:false;}
template<class T> bool umax(T& a, const T& b) {return a < b? a = b, true:false;}

const ll inf = 1e18+7;
const int N = 2e5+5;

long long find_maximum(int k, vector<vector<int>> x) {
	int n = sz(x);
	int m = sz(x[0]);
	vector<vii>v[2];
	v[0].resize(n);
	v[1].resize(n);
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++) v[x[i][j]][i].pb(j); 
	}
	ll ans = 0;
	
	vector<vii> aa(n, vii(m, 0));
	
	//for(int i=0;i<n;i++){
		//cout<<i<<" : ";
		//for(auto x:v[0][i]) cout<<x<<" ";
		//cout<<"\n";
	//}
	//cout<<"\n";
	//for(int i=0;i<n;i++){
		//cout<<i<<" : ";
		//for(auto x:v[1][i]) cout<<x<<" ";
		//cout<<"\n";
	//}
	//cout<<"\n";
	for(int i=0;i<k;i++){
		vector<int> used;
		int t1 = 0, t0 = 0;
		
		for(int j=0;j<n;j++){
			if(sz(v[0][j]) == 0) t1++;
			if(sz(v[1][j]) == 0) t0++;
		}
		for(int j=0;j<n;j++){
			if(sz(v[0][j]) == 0){
				used.pb(v[1][j].back());
				v[1][j].pop_back();
			}else if(sz(v[1][j]) == 0){
				used.pb(v[0][j].back());
				v[0][j].pop_back();
			}else{
				if(t1 < t0){
					used.pb(v[1][j].back());
					v[1][j].pop_back();
					t1++;
				}else if(t1 > t0){
					used.pb(v[0][j].back());
					v[0][j].pop_back();
					t0++;
				}else{
					if(sz(v[0][j]) > sz(v[1][j])){
						used.pb(v[0][j].back());
						v[0][j].pop_back();
						t0++;
					}else{
						used.pb(v[1][j].back());
						v[1][j].pop_back();
						t1++;
					}
				}
			}
		}
		
		//for(auto x:used) cout<<x<<" ";
		//cout<<"\n";
		
		//cout<<i<<" ";
		for(int j=0;j<n;j++){
			//cout<<used[j]<<" ";
			aa[j][used[j]] = i+1;
		} //cout<<"\n";
		
		ans += min(t0, t1);
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			aa[i][j]--;
		}
	}
	//for(int i=0;i<n;i++){
		//for(int j=0;j<m;j++){
			//cout<<aa[i][j]<<" ";
		//}cout<<endl;
	//}
	allocate_tickets(aa);
	return ans;
}
/*

4 3 2
1 1 0
0 1 1
0 0 1
0 1 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