Submission #601206

#	Time	Username	Problem	Language	Result	Execution time	Memory
601206		FatihSolak	Carnival Tickets (IOI20_tickets)	C++17	41 / 100	1149 ms	54880 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
struct BIT{
	vector<long long> bit;
	int n;
	BIT(int size){
		n = size + 5;
		bit.assign(n+5,0);
	}
	void upd(int pos,long long val){
		for(++pos;pos < n;pos += pos & -pos){
			bit[pos] += val;
		}
	}
	long long get(int pos){
		long long ret = 0;
		for(++pos;pos > 0;pos -= pos & -pos){
			ret += bit[pos];
		}
		return ret;
	}
	long long get(int l,int r){
		return get(r) - get(l-1);
	}
	int get_kth(int k){
		int pos = 0;
		for(int i = 20;i>=0;i--){
			if( (pos + (1<<i)) < n && bit[pos + (1<<i)] < k){
				k -= bit[pos + (1<<i)];
				pos += (1<<i);
			}
		}
		return pos;
	}
};
long long find_maximum(int k, vector<vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	vector<vector<int>> answer;
	for (int i = 0; i < n; i++) {
		vector<int> row(m,-1);
		answer.push_back(row);
	}
	if(k == 1){
		long long ans = 0;
		for(int i = 0;i<n;i++){
			int lcnt = 0,rcnt = 0;
			long long lsum = 0,rsum = 0;
			vector<pair<long long,int>> v;
			vector<pair<int,int>> lpoints;
			vector<pair<int,int>> rpoints;
			for(int j = 0;j<n;j++){
				if(i == j)continue;
				v.push_back({x[j][0] + x[j][m-1],j});
				lpoints.push_back({x[j][0],j});
				rpoints.push_back({x[j][m-1],j});
				rcnt++;
				rsum += x[j][m-1];
			}
			sort(v.rbegin(),v.rend());
			sort(lpoints.begin(),lpoints.end());
			sort(rpoints.begin(),rpoints.end());
			int sz = v.size();
			BIT tcnt(sz),ta(sz),tc(sz);
			vector<int> ord(n);
			int pt1 = 0,pt2 = 0;
			for(int j = 0;j<v.size();j++){
				ord[v[j].second] = j;
			}
			int neededl = n/2-1;
			int neededr = n/2;
			for(int j = 0;j<m;j++){
				while(pt1 < lpoints.size() && lpoints[pt1].first <= x[i][j]){
					rcnt--;
					rsum -= x[lpoints[pt1].second][m-1];
					tcnt.upd(ord[lpoints[pt1].second],1);
					ta.upd(ord[lpoints[pt1].second],x[lpoints[pt1].second][0]);
					tc.upd(ord[lpoints[pt1].second],x[lpoints[pt1].second][m-1]);
					pt1++;
				}
				while(pt2 < rpoints.size() && rpoints[pt2].first < x[i][j]){
					lcnt++;
					lsum += x[rpoints[pt2].second][0];
					tcnt.upd(ord[rpoints[pt2].second],-1);
					ta.upd(ord[rpoints[pt2].second],-x[rpoints[pt2].second][0]);
					tc.upd(ord[rpoints[pt2].second],-x[rpoints[pt2].second][m-1]);
					pt2++;
				}
				if(lcnt > neededl || rcnt > neededr)continue;
				long long nowans = 0;
				nowans += rsum - lsum;
				nowans -= x[i][j];
				int point = tcnt.get_kth(neededr - rcnt);
				//cout << point << " " << sz  << endl;
				//cout << nowans << endl;
				nowans += tc.get(0,point);
				nowans -= ta.get(point+1,sz-1);
				ans = max(ans,nowans);
			}
		}
		for(int i = 0;i<n;i++){
			int lcnt = 0,rcnt = 0;
			long long lsum = 0,rsum = 0;
			vector<pair<long long,int>> v;
			vector<pair<int,int>> lpoints;
			vector<pair<int,int>> rpoints;
			for(int j = 0;j<n;j++){
				if(i == j)continue;
				v.push_back({x[j][0] + x[j][m-1],j});
				lpoints.push_back({x[j][0],j});
				rpoints.push_back({x[j][m-1],j});
				rcnt++;
				rsum += x[j][m-1];
			}
			sort(v.rbegin(),v.rend());
			sort(lpoints.begin(),lpoints.end());
			sort(rpoints.begin(),rpoints.end());
			int sz = v.size();
			BIT tcnt(sz),ta(sz),tc(sz);
			vector<int> ord(n);
			int pt1 = 0,pt2 = 0;
			for(int j = 0;j<v.size();j++){
				ord[v[j].second] = j;
			}
			int neededl = n/2-1;
			int neededr = n/2;
			for(int j = 0;j<m;j++){
				while(pt1 < lpoints.size() && lpoints[pt1].first <= x[i][j]){
					rcnt--;
					rsum -= x[lpoints[pt1].second][m-1];
					tcnt.upd(ord[lpoints[pt1].second],1);
					ta.upd(ord[lpoints[pt1].second],x[lpoints[pt1].second][0]);
					tc.upd(ord[lpoints[pt1].second],x[lpoints[pt1].second][m-1]);
					pt1++;
				}
				while(pt2 < rpoints.size() && rpoints[pt2].first < x[i][j]){
					lcnt++;
					lsum += x[rpoints[pt2].second][0];
					tcnt.upd(ord[rpoints[pt2].second],-1);
					ta.upd(ord[rpoints[pt2].second],-x[rpoints[pt2].second][0]);
					tc.upd(ord[rpoints[pt2].second],-x[rpoints[pt2].second][m-1]);
					pt2++;
				}
				if(lcnt > neededl || rcnt > neededr)continue;
				long long nowans = 0;
				nowans += rsum - lsum;
				nowans -= x[i][j];
				int point = tcnt.get_kth(neededr - rcnt);
				//cout << point << " " << sz  << endl;
				//cout << nowans << endl;
				nowans += tc.get(0,point);
				nowans -= ta.get(point+1,sz-1);
				if(nowans == ans){
					vector<int> use(n,-1);
					for(int c = 0;c<=point;c++){
						if(tcnt.get(c,c)){
							use[v[c].second] = m-1;
						}
					}
					for(int c = point+1;c<=sz-1;c++){
						if(tcnt.get(c,c)){
							use[v[c].second] = 0;
						}
					}
					for(int c = 0;c<n;c++){
						if(i == c){
							answer[i][j] = 0;
							continue;
						}
						if(use[c] != -1){
							answer[c][use[c]] = 0;
							continue;
						}
						if(x[c][m-1] < x[i][j]){
							answer[c][0] = 0;
						}
						else answer[c][m-1] = 0;
					}
					allocate_tickets(answer);
					return ans;
				}
			}
		}
	}
	int maxi = 0;
	for(int i = 0;i<n;i++){
		for(int j = 0;j<m;j++){
			maxi = max(maxi,x[i][j]);
		}
	}
	if(maxi <= 1){
		vector<int> cnt0(n),cnt1(n);
		vector<int> lp(n),rp(n);
		for(int i = 0;i<n;i++){
			lp[i] = 0;
			rp[i] = m-1;
			for(int j = 0;j<m;j++){
				if(x[i][j] == 0){
					cnt0[i]++;
				}
				if(x[i][j] == 1){
					cnt1[i]++;
				}
			}
		}
		long long ans = 0;
		for(int x = 0;x<k;x++){
			set<pair<int,int>> s0,s1;
			for(int i = 0;i<n;i++){
				s0.insert({cnt0[i],i});
				s1.insert({cnt1[i],i});
			}
			int now0 = 0,now1=0;
			while(now0 + now1 < n){
				int use = (s0.rbegin()->first == 0) || (s1.rbegin()->first != 0 && now0 > now1);
				if(use == 0){
					now0++;
					int point = s0.rbegin()->second;
					s0.erase({cnt0[point],point});
					s1.erase({cnt1[point],point});
					cnt0[point]--;
					answer[point][lp[point]++] = x;
				}
				if(use == 1){
					now1++;
					int point = s1.rbegin()->second;
					s0.erase({cnt0[point],point});
					s1.erase({cnt1[point],point});
					cnt1[point]--;
					answer[point][rp[point]--] = x;
				}
			}
			ans += min(now0,now1);
		}
		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:68:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |    for(int j = 0;j<v.size();j++){
      |                  ~^~~~~~~~~
tickets.cpp:74:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     while(pt1 < lpoints.size() && lpoints[pt1].first <= x[i][j]){
      |           ~~~~^~~~~~~~~~~~~~~~
tickets.cpp:82:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     while(pt2 < rpoints.size() && rpoints[pt2].first < x[i][j]){
      |           ~~~~^~~~~~~~~~~~~~~~
tickets.cpp:123:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |    for(int j = 0;j<v.size();j++){
      |                  ~^~~~~~~~~
tickets.cpp:129:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |     while(pt1 < lpoints.size() && lpoints[pt1].first <= x[i][j]){
      |           ~~~~^~~~~~~~~~~~~~~~
tickets.cpp:137:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |     while(pt2 < rpoints.size() && rpoints[pt2].first < x[i][j]){
      |           ~~~~^~~~~~~~~~~~~~~~
tickets.cpp:40:22: warning: control reaches end of non-void function [-Wreturn-type]
   40 |  vector<vector<int>> answer;
      |                      ^~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 16 / 16
• Subtask 3: 14 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23
• Subtask 7: 0 / 10