oj.uz

Submission #1072937

# Submission time Handle Problem Language Result Execution time Memory
1072937 2024-08-24T07:34:05 Z LCJLY Carnival Tickets (IOI20_tickets) C++14
25 / 100
 1219 ms 326868 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;
		//show2(x,x,ptr[x],ptr[x]);
			
		int cur=0;
		for(int y=min((int)k,(int)lft[x].size())-1;y>=0;y--){
			v2.push_back({lft[x][y].first+arr[x][ptr[x]-cur],x});
			//show2(x,x,y,y);
			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]--;
	}
	
	//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 0 ms 348 KB Output is correct
6 Correct 2 ms 1116 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Contestant returned 428553445 while correct return value is 2727881086.
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 352 KB Output is correct
3 Runtime error 1 ms 348 KB Execution killed with signal 11
4 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 1 ms 348 KB Output is correct
4 Correct 3 ms 1312 KB Output is correct
5 Correct 40 ms 15280 KB Output is correct
6 Correct 6 ms 2484 KB Output is correct
7 Correct 9 ms 3000 KB Output is correct
8 Correct 1219 ms 326868 KB Output is correct
9 Correct 1130 ms 309848 KB Output is correct
10 Correct 1057 ms 301512 KB Output is correct
11 Correct 1160 ms 323296 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 2 ms 1056 KB Contestant returned 1167375429 while correct return value is 39376297182.
3 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 2 ms 1056 KB Contestant returned 1167375429 while correct return value is 39376297182.
3 Halted 0 ms 0 KB -

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 0 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 Incorrect 0 ms 348 KB Contestant returned 428553445 while correct return value is 2727881086.
9 Halted 0 ms 0 KB -