Submission #431928

#	Time	Username	Problem	Language	Result	Execution time	Memory
431928		Pbezz	Carnival Tickets (IOI20_tickets)	C++14	0 / 100	1 ms	204 KiB

tickets

#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
typedef pair<ll,ll> pii;

const ll MAXN = 2e5+5;
const ll INF = 1e9+7;

bool used[MAXN]={false};
int bruh[MAXN];
long long find_maximum(int k, std::vector<std::vector<int>> x) {
	int n = x.size(),i,j;	
	int m = x[0].size();

	vector<int>ans; vector<pii>maybe;
	for(j=0;j<n;j++){
	maybe.pb({x[j][0],j});
	maybe.pb({x[j][m-1],j});
	}
	sort(maybe.begin(),maybe.end());

	ll cur1=0,cur2=2*n-1;
	for(i=0;i<(n/2);i++){

	while(cur2>=0 && used[cur2])cur2--;
	while(cur1<2*n && used[cur1])cur1++;

	if(maybe[cur2].second==maybe[cur1].second){

if(maybe[cur2].first-maybe[cur1+1].first>maybe[cur2-1].first-maybe[cur1].first){

	ans.pb(maybe[cur2].first);
	ans.pb(maybe[cur1+1].first);
	used[cur2]=true;
	used[cur1+1]=true; cur1++;
	bruh[maybe[cur2].second]=m-1;
	bruh[maybe[cur1].second]=0;
	}else{

	ans.pb(maybe[cur2-1].first);
	ans.pb(maybe[cur1].first);
	used[cur2-1]=true; cur2--;
	used[cur1]=true;
	bruh[maybe[cur2].second]=m-1;
	bruh[maybe[cur1].second]=0;
	}

	}else{

	ans.pb(maybe[cur2].first);
	ans.pb(maybe[cur1].first);
	used[cur2]=true;
	used[cur1]=true;
	bruh[maybe[cur2].second]=m-1;
	bruh[maybe[cur1].second]=0;

	}

//cout<<i<<" "<<cur1<<" "<<maybe[cur1].first<<" "<<maybe[cur1].second<<" ";
//cout<<" "<<cur2<<" "<<maybe[cur2].first<<" "<<maybe[cur2].second<<endl;

	}

	sort(ans.begin(),ans.end());
	ll res=0;
	for(i=0;i<n;i++){
	res+=abs(ans[i]-ans[n/2]);
	}

	std::vector<std::vector<int>> answer;

	for(i=0;i<n;i++){
	vector<int>row(m);
	for(j=0;j<m;j++){
	if(j==bruh[i]){
	row[j]=0;
	}else{
	row[j]=-1;
	}
	}

	answer.pb(row);

	}



	allocate_tickets(answer);





	return res;
}

• 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