Submission #583090

#	Time	Username	Problem	Language	Result	Execution time	Memory
583090		hail	Carnival Tickets (IOI20_tickets)	C++17	11 / 100	2 ms	852 KiB

tickets

#include <bits/stdc++.h>

using namespace std;

void allocate_tickets(vector<vector<int>> s);

using ind_min_max = pair<int, pair<int, int>>;

struct abs_d_comp
{
	int abs_d;
	ind_min_max over;
	ind_min_max under;
};

bool compare_max(ind_min_max a, ind_min_max b)
{
    return a.second.second>b.second.second;
}

bool compare_min(ind_min_max a, ind_min_max b)
{
    return a.second.first<b.second.first;
}

bool compare_r(abs_d_comp a, abs_d_comp b)
{
	return abs(a.abs_d)<abs(b.abs_d);
}



long long find_maximum(int k, vector<vector<int>> x)
{


    int n = x.size();
    int m = x[0].size();

	vector<vector<int>> dupli{x};

    
    vector<int> initial(m, -1);
	vector<vector<int>> answer(n, initial);

	vector<ind_min_max> min_max(0);
	vector<int> occurrences(n, 0);
	vector<int> dummy(n, 0);

	vector<ind_min_max> max_des(0);
	vector<ind_min_max> min_asc(0);

	vector<ind_min_max> oversel(0);
	vector<ind_min_max> undersel(0);

	abs_d_comp inp;
	abs_d_comp re;

	vector<abs_d_comp> replacements(0);
	vector<abs_d_comp> replacements_new(0);

	vector<ind_min_max> max_sel(0);
	vector<ind_min_max> min_sel(0);

	for(int i=0; i<k; i++)
	{
		min_max.clear();
		occurrences=dummy;
		replacements.clear();
		oversel.clear();
		undersel.clear();
		max_sel.clear();
		min_sel.clear();
		for(int j=0; j<n; j++)
		{
			min_max.push_back(make_pair(j, make_pair(x[j][0], x[j][m-i-1])));
		}

		max_des = min_max;
		sort(max_des.begin(), max_des.end(), compare_max);

		min_asc = min_max;
		sort(min_asc.begin(), min_asc.end(), compare_min);

		for(int j=0; j<(n/2); j++)
		{
			occurrences[max_des[j].first]++;
			occurrences[min_asc[j].first]++;
		}

		for(int j=0; j<n; j++)
		{
			if(occurrences[j]==2)
			{
				oversel.push_back(min_max[j]);
			}
			else if(occurrences[j]==0)
			{
				undersel.push_back(min_max[j]);
			}
			else if(occurrences[j]==1)
			{
				if(find(min_asc.begin(), min_asc.begin()+(n/2), min_max[j])==min_asc.begin()+(n/2))
				{
					max_sel.push_back(min_max[j]);
				}
				else
				{
					min_sel.push_back(min_max[j]);
				}
			}
		}

		for(ind_min_max over: oversel)
		{
			for(ind_min_max under: undersel)
			{
				inp.over = over;
				inp.under = under;
				inp.abs_d = abs(over.second.second - under.second.second);
				replacements.push_back(inp);
				inp.abs_d = (-1)*abs(over.second.first - under.second.first);
				replacements.push_back(inp);
			}
		}

		sort(replacements.begin(), replacements.end(), compare_r);

		while(not replacements.empty())
		{
			re = replacements[0];
			replacements_new.clear();
			if(re.abs_d>=0)
			{
				max_sel.push_back(re.under);
				min_sel.push_back(re.over);
			}
			else
			{
				max_sel.push_back(re.over);
				min_sel.push_back(re.under);
			}

			for(abs_d_comp bla: replacements)
			{
				if(not (bla.over==re.over || bla.under==re.under))
				{
					replacements_new.push_back(bla);
				}
			}
			replacements=replacements_new;

		}

		for(ind_min_max bla: max_sel)
		{
			for(int j=m-1; j>=0; j--)
			{
				if(answer[bla.first][j]==(-1))
				{
					answer[bla.first][j]=i;
					break;
				}
			}
			x[bla.first].erase(x[bla.first].end()-1);
		}
		for(ind_min_max bla: min_sel)
		{
			for(int j=0; j<m; j++)
			{
				if(answer[bla.first][j]==-1)
				{
					answer[bla.first][j]=i;
					break;
				}
			}
			x[bla.first].erase(x[bla.first].begin());
		}

	}

	allocate_tickets(answer);

	long long max_sum = 0;
	set<int> summate;
	for(int i=0; i<k; i++)
	{
		summate.erase(summate.begin(), summate.end());
		for(int a=0; a<n; a++)
		{
			for(int b=0; b<m; b++)
			{
				if(answer[a][b]==i)
				{
					summate.insert(dupli[a][b]);
				}
			}
		}
		int counter{};
		auto median_it(summate.begin());
		for(auto it=summate.begin(); it!= summate.end(); it++)
		{
			counter++;
			if(counter==(n/2))
			{
				median_it=it;
				break;
			}

		}
		for(auto it=summate.begin(); it!=summate.end(); it++)
		{
			max_sum += abs((*it)-(*median_it));
		}
	}

	

	return max_sum;


	


}    

• 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