Submission #800649

#	Time	Username	Problem	Language	Result	Execution time	Memory
800649		APROHACK	Carnival Tickets (IOI20_tickets)	C++17	0 / 100	1 ms	212 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;
void use(int color, bool fst, int round){
	if(fst){
		answer[color][first[color]] = round;
		first[color] ++;
	}else{
		answer[color][last[color]] = round;
		last[color] --;
	}
}



 
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;
	
	vector<deque<ll>>X;
	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;
		int c00 = 0, c01 = 0, c11 = 0;
		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(), true, r);
				v01.pop_back();
				use(v01.back(), false, 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;
}

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:47:7: warning: unused variable 'c00' [-Wunused-variable]
   47 |   int c00 = 0, c01 = 0, c11 = 0;
      |       ^~~
tickets.cpp:47:16: warning: unused variable 'c01' [-Wunused-variable]
   47 |   int c00 = 0, c01 = 0, c11 = 0;
      |                ^~~
tickets.cpp:47:25: warning: unused variable 'c11' [-Wunused-variable]
   47 |   int c00 = 0, c01 = 0, c11 = 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