oj.uz

Submission #1072950

# Submission time Handle Problem Language Result Execution time Memory
1072950 2024-08-24T07:45:33 Z LCJLY Carnival Tickets (IOI20_tickets) C++14
76 / 100
 1205 ms 300652 KB 
#include <bits/stdc++.h>
#include "tickets.h"
//#include "grader.cpp"
using namespace std;
 
#define int long long
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<long long,long long>pii;
typedef pair<long long,pii>pi2;
 
//allocate_tickets(vector<vector<int>>)
 
long long find_maximum(int32_t k, vector<vector<int32_t>>arr){
	int n=arr.size();
	int m=arr[0].size();
	vector<pi2>v;
	int ptr[n];
	for(int x=0;x<n;x++){
		for(int y=0;y<m;y++){
			v.push_back({arr[x][y],{x,y}});
		}
		ptr[x]=m-1;
	}
	sort(v.begin(),v.end());
	vector<pi2>lft[n+5];
	vector<pi2>rgt[n+5];
	for(int x=0;x<n*m/2;x++){
		lft[v[x].second.first].push_back(v[x]);
		rgt[v[x+n*m/2].second.first].push_back(v[x+n*m/2]);
	}
	
	vector<pii>v2;
	int l=0;
	for(int x=0;x<n;x++){
		int hold=max(0LL,k-(int)lft[x].size());
		ptr[x]-=hold;
			
		int cur=0;
		for(int y=min((int)k,(int)lft[x].size())-1;y>=0;y--){
			//assert(y<ptr[x]-cur);
			if(y>=ptr[x]-cur) break;
			v2.push_back({lft[x][y].first+arr[x][ptr[x]-cur],x});
			cur++;
			l++;
		}
	}
	//show(l,l);
	sort(v2.begin(),v2.end());
	reverse(v2.begin(),v2.end());
	//for(auto it:v2){
		//show2(it.first,it.first,it.second,it.second);
	//}
	int index=0;
	while(l>k*n/2){
		l--;
		ptr[v2[index].second]--;
		index++;
	}
	
	//for(int x=0;x<n;x++){
		//show2(x,x,ptr[x],ptr[x]);
	//}
	
	{
		vector<pi2>v;
		for(int x=0;x<n;x++){
			for(int y=m-1;y>ptr[x];y--){
				v.push_back({arr[x][y],{x,y}});
			}
			for(int y=0;y<k-(m-1-ptr[x]);y++){
				v.push_back({arr[x][y],{x,y}});
			}			
		}
		
		sort(v.begin(),v.end());
		int counter=0;
		for(int x=0;x<k*n/2;x++){
			counter+=abs(v[x].first-v[k*n-1-x].first);
		}
		int cnt[n+5];
		memset(cnt,0,sizeof(cnt));
		vector<pi2>storage[n+5];
		vector<pi2>storage2[n+5];
		for(int x=0;x<k*n/2;x++){
			cnt[v[x].second.first]++;
			storage[v[x].second.first].push_back(v[x]);
			storage2[v[x+k*n/2].second.first].push_back(v[x+k*n/2]);
		}
	 
		priority_queue<pii>pq;
		for(int x=0;x<n;x++){
			pq.push({cnt[x],x});
		}
		
		vector<vector<int32_t>>ans;
		ans.resize(n);
		for(int x=0;x<n;x++) ans[x]=vector<int32_t>(m,-1);
		
		for(int x=0;x<k;x++){
			bool take[n+5];
			memset(take,0,sizeof(take));
			vector<pii>temp;
			for(int y=0;y<n/2;y++){
				pii cur=pq.top();
				pq.pop();
				take[cur.second]=true;
				cur.first--;
				temp.push_back(cur);
				pi2 take=storage[cur.second].back();
				storage[cur.second].pop_back();
				ans[take.second.first][take.second.second]=x;
			}
			for(int y=0;y<n;y++){
				if(take[y]) continue;
				pi2 take=storage2[y].back();
				storage2[y].pop_back();
				ans[take.second.first][take.second.second]=x;
			}
			for(auto it:temp) pq.push(it);
		}
		allocate_tickets(ans);
		return counter;
	}
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 1116 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 800 KB Output is correct
5 Correct 22 ms 8140 KB Output is correct
6 Correct 605 ms 166792 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 1052 KB Output is correct
5 Incorrect 29 ms 11460 KB Contestant returned 22496 while correct return value is 22500.
6 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 3 ms 1248 KB Output is correct
5 Correct 34 ms 14584 KB Output is correct
6 Correct 6 ms 2412 KB Output is correct
7 Correct 8 ms 2904 KB Output is correct
8 Correct 1114 ms 298468 KB Output is correct
9 Correct 1016 ms 288472 KB Output is correct
10 Correct 1062 ms 280412 KB Output is correct
11 Correct 1205 ms 300652 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 3 ms 844 KB Output is correct
3 Correct 4 ms 1056 KB Output is correct
4 Correct 4 ms 1056 KB Output is correct
5 Correct 2 ms 1312 KB Output is correct
6 Correct 3 ms 1312 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 3 ms 1160 KB Output is correct
10 Correct 3 ms 1312 KB Output is correct
11 Correct 3 ms 1296 KB Output is correct
12 Correct 4 ms 1312 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 3 ms 844 KB Output is correct
3 Correct 4 ms 1056 KB Output is correct
4 Correct 4 ms 1056 KB Output is correct
5 Correct 2 ms 1312 KB Output is correct
6 Correct 3 ms 1312 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 3 ms 1160 KB Output is correct
10 Correct 3 ms 1312 KB Output is correct
11 Correct 3 ms 1296 KB Output is correct
12 Correct 4 ms 1312 KB Output is correct
13 Correct 22 ms 8896 KB Output is correct
14 Correct 34 ms 9164 KB Output is correct
15 Correct 49 ms 12484 KB Output is correct
16 Correct 35 ms 14648 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 3 ms 1152 KB Output is correct
19 Correct 2 ms 600 KB Output is correct
20 Correct 35 ms 11712 KB Output is correct
21 Correct 42 ms 11944 KB Output is correct
22 Correct 37 ms 12980 KB Output is correct
23 Correct 35 ms 13248 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 1116 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 2 ms 800 KB Output is correct
11 Correct 22 ms 8140 KB Output is correct
12 Correct 605 ms 166792 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 2 ms 1052 KB Output is correct
17 Incorrect 29 ms 11460 KB Contestant returned 22496 while correct return value is 22500.
18 Halted 0 ms 0 KB -