oj.uz

답안 #601206

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
601206 2022-07-21T13:08:42 Z FatihSolak 카니발 티켓 (IOI20_tickets) C++17
41 / 100
 1149 ms 54880 KB 
#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

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.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 19 ms 340 KB Output is correct
6 Correct 784 ms 764 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 45 ms 2312 KB Output is correct
6 Correct 1149 ms 51440 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 29 ms 2484 KB Output is correct
6 Correct 747 ms 53820 KB Output is correct
7 Correct 871 ms 54212 KB Output is correct
8 Correct 5 ms 468 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 300 KB Output is correct
11 Correct 1 ms 540 KB Output is correct
12 Correct 9 ms 756 KB Output is correct
13 Correct 30 ms 2116 KB Output is correct
14 Correct 30 ms 2108 KB Output is correct
15 Correct 979 ms 54880 KB Output is correct

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 19 ms 340 KB Output is correct
6 Correct 784 ms 764 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 45 ms 2312 KB Output is correct
12 Correct 1149 ms 51440 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 3 ms 468 KB Output is correct
17 Correct 29 ms 2484 KB Output is correct
18 Correct 747 ms 53820 KB Output is correct
19 Correct 871 ms 54212 KB Output is correct
20 Correct 5 ms 468 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 300 KB Output is correct
23 Correct 1 ms 540 KB Output is correct
24 Correct 9 ms 756 KB Output is correct
25 Correct 30 ms 2116 KB Output is correct
26 Correct 30 ms 2108 KB Output is correct
27 Correct 979 ms 54880 KB Output is correct
28 Runtime error 2 ms 468 KB Execution killed with signal 6
29 Halted 0 ms 0 KB -