Submission #803055

#	Time	Username	Problem	Language	Result	Execution time	Memory
803055		Edu175	Carnival Tickets (IOI20_tickets)	C++17	11 / 100	3 ms	6740 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,ioi=b;i<ioi;i++)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define imp(v) for(auto dfh:v)cout<<dfh<<" ";cout<<"\n"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
const ll MAXN=1505;

ll a[MAXN][MAXN];
vector<vector<int>> us; // i,j used in round us[i][j]
ll n,m,k;
ll c[MAXN][2];
set<ll>pos[MAXN];
void useij(ll i, ll j, ll idx){
	us[i][j]=idx;
	pos[i].erase(j);
	c[i][a[i][j]]--;
}
/*void use(ll i, ll x, ll idx){ //from row i use element = to x in oper idx
	fore(j,0,m){
		if(us[i][j]==-1&&a[i][j]==x){
			us[i][j]=idx;
			pos[i].erase(j);
			return;
		}
	}
	assert(0);
}*/
/*void use_all(ll x, ll idx){ //if can use x in every row
	vector<ll>op;
	fore(i,0,n){
		for(auto j:pos){
			if(!c[i][x]){
				op.pb(j);
				break;
			}
			else {
				if(a[i][j]==x){
					op.pb(j);
					break;
				}
			}
		}
	}
	fore(i,0,SZ(op))useij(i,op[i],idx);
}*/
long long find_maximum(int K, std::vector<std::vector<int>> A){
	k=K;
	n=SZ(A);
	m=SZ(A[0]);
	fore(i,0,n)fore(j,0,m)a[i][j]=A[i][j];
	us.resize(n,vector<int>(m,-1));
	if(m==1){
		//sub m=1
		vector<ll>b;
		fore(i,0,n)b.pb(a[i][0]),us[i][0]=0;
		sort(ALL(b));
		ll sum=0;
		fore(i,0,n)sum+=abs(b[i]-b[n/2]);
		allocate_tickets(us);
		return sum;
	}
	//ll is_sub=1;
	//fore(i,0,n)fore(j,0,m)if(a[i][j]>1)is_sub=0;
	fore(i,0,n)fore(j,0,m)c[i][a[i][j]]++;
	fore(i,0,n)fore(j,0,m)pos[i].insert(j);
	ll res=0;
	fore(idx,0,k){
		vector<ll>q(2);
		fore(i,0,n){
			if(!c[i][0])q[1]++;
			if(!c[i][1])q[0]++;
		}
		vector<ll>u(2);
		if(q[0]>=n/2)u[0]=0,u[1]=n-q[0]-q[1];
		else if(q[1]>=n/2)u[1]=0,u[0]=n-q[0]-q[1];
		else u[0]=n/2-q[0],u[1]=n/2-q[1];
		res+=min(q[0]+u[0],q[1]+u[1]);
		fore(i,0,n){
			if(!c[i][0])useij(i,*pos[i].begin(),idx);
			else if(!c[i][1])useij(i,*pos[i].begin(),idx);
			else {
				for(auto j:pos[i])if(u[a[i][j]]){
					useij(i,j,idx),u[a[i][j]]--;
					break;
				}
			}
		}
	}
	allocate_tickets(us);
	return res;
}

• 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