Submission #601226

#	Time	Username	Problem	Language	Result	Execution time	Memory
601226		FatihSolak	Carnival Tickets (IOI20_tickets)	C++17	Compilation error	0 ms	0 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>> tmp = x;
	vector<vector<int>> pos = x;
	for(int i = 0;i<n;i++){
		for(int j = 0;j<m;j++){
			pos[i][j] = j;
		}
	}
	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 xx = 0;xx<k;xx++){
			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]++] = xx;
				}
				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]--] = xx;
				}
			}
			ans += min(now0,now1);
		}
		allocate_tickets(answer);
		return ans;
	}
	long long tot_ans = 0;
	for(int xx = 0;xx<k;xx++){
		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);
			}
		}
		tot_ans += ans;
		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[c][pos[c][j]] = xx;
							continue;
						}
						if(use[c] != -1){
							answer[c][pos[c][use[c]]] = xx;
							continue;
						}
						if(x[c][m-1] < x[i][j]){
							answer[c][pos[c][0]] = xx;
						}
						else answer[c][pos[c][m-1]] = xx;
					}
					ans = -1;
				}
			}
		}
		vector<vector<int>> nwx = x;
		vector<vector<int>> nwpos = pos;
		for(int i = 0;i<n;i++){
			int tot = 0;
			for(int j = 0;j<m;j++){
				if(answer[i][pos[i][j]] == -1){
					nwx[i][tot] = x[i][j];
					nwpos[i][tot++] = pos[i][j];
				}
			}
		}
		x = nwx;
		pos = nwpos;
		m--;
	}
	x = tmp;
	m = x[0].size();
	for(int i = 0;i<n;i++){
		for(j = 0;j<m;j++){
			answer[i][j] = j;
		}
	}
	allocate_tickets(answer);
	return tot_ans;
}

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:75: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]
   75 |    for(int j = 0;j<v.size();j++){
      |                  ~^~~~~~~~~
tickets.cpp:81: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]
   81 |     while(pt1 < lpoints.size() && lpoints[pt1].first <= x[i][j]){
      |           ~~~~^~~~~~~~~~~~~~~~
tickets.cpp:89: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]
   89 |     while(pt2 < rpoints.size() && rpoints[pt2].first < x[i][j]){
      |           ~~~~^~~~~~~~~~~~~~~~
tickets.cpp:130: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]
  130 |    for(int j = 0;j<v.size();j++){
      |                  ~^~~~~~~~~
tickets.cpp:136: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]
  136 |     while(pt1 < lpoints.size() && lpoints[pt1].first <= x[i][j]){
      |           ~~~~^~~~~~~~~~~~~~~~
tickets.cpp:144: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]
  144 |     while(pt2 < rpoints.size() && rpoints[pt2].first < x[i][j]){
      |           ~~~~^~~~~~~~~~~~~~~~
tickets.cpp:270: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]
  270 |    for(int j = 0;j<v.size();j++){
      |                  ~^~~~~~~~~
tickets.cpp:276: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]
  276 |     while(pt1 < lpoints.size() && lpoints[pt1].first <= x[i][j]){
      |           ~~~~^~~~~~~~~~~~~~~~
tickets.cpp:284: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]
  284 |     while(pt2 < rpoints.size() && rpoints[pt2].first < x[i][j]){
      |           ~~~~^~~~~~~~~~~~~~~~
tickets.cpp:326: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]
  326 |    for(int j = 0;j<v.size();j++){
      |                  ~^~~~~~~~~
tickets.cpp:332: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]
  332 |     while(pt1 < lpoints.size() && lpoints[pt1].first <= x[i][j]){
      |           ~~~~^~~~~~~~~~~~~~~~
tickets.cpp:340: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]
  340 |     while(pt2 < rpoints.size() && rpoints[pt2].first < x[i][j]){
      |           ~~~~^~~~~~~~~~~~~~~~
tickets.cpp:405:7: error: 'j' was not declared in this scope
  405 |   for(j = 0;j<m;j++){
      |       ^