제출 #800669

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
800669		APROHACK	카니발 티켓 (IOI20_tickets)	C++17	11 / 100	1 ms	596 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;
int n, m, K;
vector<int>first, last;
vector<std::vector<int>> answer;
vector<deque<ll>>X;
void use(int color, bool fst, int round){
	if(fst){
		answer[color][first[color]] = round;
		first[color] ++;
		X[color].pop_back();
	}else{
		answer[color][last[color]] = round;
		last[color] --;
		X[color].pop_front();
	}
}



 
long long find_maximum(int k, std::vector< std::vector<int> > x) {
	n = x.size();
	m = x[0].size();
	K = k;
	
	vector<int>row;
	for(int i = 0 ; i < n ; i ++){
		first.pb(0);
		last.pb(m-1);
	}
	for(int i = 0 ; i < m ; i ++)row.pb(-1);
	for(int i  = 0 ; i < n ; i ++)answer.pb(row);
	ll ans = 0;
	if(m == 1){
		for(int r = 0 ; r < k ; r ++){
			vector<ll>acum;
			for(int i = 0 ; i < n ; i ++){
				answer[i][r] = r;
				acum.pb(x[i][r]);
			}
			sort(acum.begin(), acum.end());
			
			for(int i = 0, j = n-1;  i < j; i ++, j--){\
				ans += acum[j] - acum[i];
			}
		}
		allocate_tickets(answer);
		return ans;
	}
	
	
	for(int i = 0 ; i < n ; i ++){
		deque<ll>cur;
		for(int j = 0 ; j < m ; j ++)cur.push_front(x[i][j]);
		X.pb(cur);
	}
	
	for(int r = 0 ; r < k ; r ++){
		vector<ll>acum;
		vector<int>v00, v01, v11;
		for(int i = 0 ; i < n ; i ++){
			if(X[i].back() == 0 and X[i].front() == 0)v00.pb(i);
			else if(X[i].back() == 0 and X[i].front() == 1)v01.pb(i);
			else v11.pb(i);
		}
		//cout << "initially 00 = " << v00.size() << " 11 = " << v11.size() << " 01 = " << v01.size() << endl;
		int cuenta = min(v00.size(), v11.size());
		ans += cuenta;
		for(int i = 0 ; i < cuenta ; i ++){
			use(v00.back(), true, r);
			use(v11.back(), false, r);
			v00.pop_back();
			v11.pop_back();
		}
		cuenta = min(max((int)v00.size(), (int)v11.size()), (int)v01.size());
		ans += cuenta;
		if(v00.size() > v11.size()){
			for(int i = 0 ; i < cuenta ; i ++){
				use(v00.back(), true, r);
				use(v01.back(), false, r);
				v00.pop_back();
				v01.pop_back();
			}
		}else if(v00.size() < v11.size()){
			for(int i = 0 ; i < cuenta ; i ++){
				use(v11.back(), true, r);
				use(v01.back(), true, r);
				v11.pop_back();
				v01.pop_back();
			}
		}
		if(v00.size() == 0 and v11.size() == 0){
			cuenta = v01.size();
			ans += cuenta/2;
			for(int i = 0 ; i < cuenta ; i += 2){
				use(v01.back(), false, r);
				v01.pop_back();
				if(v01.empty())break;
				use(v01.back(), true, r);
				v01.pop_back();
			}
		}else if(v00.size() > 0){
			cuenta = v00.size();
			for(int i = 0 ; i < cuenta ; i ++){
				use(v00.back(), true, r);
				v00.pop_back();
			}
		}else{
			cuenta = v11.size();
			for(int i = 0 ; i < cuenta ; i ++){
				use(v11.back(), true, r);
				v11.pop_back();
			}
		}
	}
	allocate_tickets(answer);
	return ans;
}

• Subtask 1: 11 / 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