oj.uz

Submission #302625

# Submission time Handle Problem Language Result Execution time Memory
302625 2020-09-18T23:51:53 Z aljasdlas Carnival Tickets (IOI20_tickets) C++14
27 / 100
 1207 ms 88696 KB 
#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;

#define int long long


int n;
int m;
vector<deque<pair<int,int>>> v;
vector<vector<signed>> answer;

int calcScore(vector<int> inp) {
	if(inp.empty()) return 0;

	vector<int> temp;
	for(auto x: inp)
		temp.push_back(x);

	int cur = 0;
	sort(temp.begin(), temp.end());
	int idx = temp.size()/2;
	for(auto x: temp)
		cur += abs(x - temp[idx]);
	return cur;
}

vector<bool> used(n, 0);
vector<int> usedLower, usedUpper;
vector<pair<int,int>> diffs;
int solve(int idx, bool isLow) {
	int X = v[idx].front().first;
	if(!isLow)
		X = v[idx].back().first;
	
	used.assign(n, 0);
	usedLower.clear();
	usedUpper.clear();

	for(int i = 0; i < n; i++) {
		if(i == idx) {
			used[i] = 1;
		}
		if(v[i].front().first > X) {
			used[i] = 1;
			usedUpper.push_back(i);
		}
		if(v[i].back().first < X) {
			used[i] = 1;
			usedLower.push_back(i);
		}
	}

	diffs.clear();
	for(int i = 0; i < n; i++) {
		if(used[i]) continue;
		diffs.push_back({abs( (X-v[i].front().first) - (v[i].back().first-X)) , i});
	}
	sort(diffs.rbegin(), diffs.rend());

	for(auto p: diffs) {
		if(p.first == 0)
			break;
		if(usedLower.size() * 2 >= n) break;
		if(usedUpper.size() * 2 >= n) break;

		used[p.second] = 1;

		if(X-v[p.second].front().first > v[p.second].back().first-X) {
			usedLower.push_back(p.second);
		} else {
			usedUpper.push_back(p.second);
		}
	}

	for(int i = 0; i < n; i++) {
		if(used[i]) continue;
		if(usedLower.size() < usedUpper.size())
			usedLower.push_back(i);
		else
			usedUpper.push_back(i);
	}

	int cur = 0;
	for(auto i: usedLower)
		cur += X-v[i].front().first;
	for(auto i: usedUpper)
		cur += v[i].back().first-X;

	if(usedLower.size() * 2 > n || usedUpper.size() * 2 > n) return -1;

	// cerr << X << ":\n";
	// for(auto i: usedLower)
	// 	cerr << v[i].front().first << " ";
	// cerr << endl;
	// for(auto i: usedUpper)
	// 	cerr << v[i].back().first << " ";
	// cerr << endl;
	// cerr << "cur: " << cur << endl;
	// cerr << endl;

	return cur;
}

long long find_maximum(signed k, vector<vector<signed>> x) {
	n = x.size();
	m = x[0].size();
	answer.assign(n, vector<signed>(m, -1));
	v.assign(n, deque<pair<int,int>>(m) );

	// vector<pair<int,int>> v;
	// for(int i = 0; i < n; i++) {
		// v.push_back({x[i], i});
	// }
	// sort(v.begin(), v.end());
	// for(int i = 0; i < n)

	// for (int i = 0; i < n; i++) {
	// 	for (int j = 0; j < m; j++) {
	// 		if (j < k) {
	// 			answer[i][j] = j;
	// 		} else {
	// 			answer[i][j] = -1;
	// 		}
	// 	}
	// }

	
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			v[i][j] = make_pair(x[i][j], j);
		}
		sort(v[i].begin(), v[i].end());
	}

	int ans2 = 0;
	for(int r = 0; r < k; r++) {
		// int lowMid = -1;
		// int highMid = 1ll<<60;
		// set<pair<int,int>> findLowMid;
		// for(int i = 0; i < n; i++)
		// 	findLowMid.insert(v[i].front());
		// while((findLowMid.size()-1)*2 > n)
		// 	findLowMid.erase(findLowMid.begin());
		// lowMid = findLowMid.begin()->first;

		// set<pair<int,int>> findHighMid;
		// for(int i = 0; i < n; i++)
		// 	findHighMid.insert(v[i].back());
		// while((findHighMid.size())*2 > n)
		// 	findHighMid.erase(findHighMid.begin());
		// highMid = findHighMid.begin()->first;

		// vector<pair<int,int>> possiblePivots;
		// for(int i = 0; i < n; i++) {
		// 	if(v[i].front().first >= lowMid && v[i].front().first <= highMid)
		// 		possiblePivots.push_back(v[i].front());
		// 	if(v[i].back().first >= lowMid && v[i].back().first <= highMid)
		// 		possiblePivots.push_back(v[i].back());
		// }
		// for(auto p: possiblePivots)
		// 	cerr << p.first << " ";
		// cerr << endl;

		int best = 0;
		int bestIdx = 0;
		int bestIsLow = 0;
		for(int i = 0; i < n; i++) {
			
			int cur = solve(i, 1);
			if(cur > best) {
				best = cur;
				bestIdx = i;
				bestIsLow = 1;
			}
			
			cur = solve(i, 0);
			if(cur > best) {
				best = cur;
				bestIdx = i;
				bestIsLow = 0;
			}
		}
		solve(bestIdx, bestIsLow);
		
		for(auto i: usedLower) {
			answer[i][ v[i].front().second ] = r;
			v[i].pop_front();
		}
		for(auto i: usedUpper) {
			answer[i][ v[i].back().second ] = r;
			v[i].pop_back();
		}
		if(bestIsLow) {
			answer[bestIdx][ v[bestIdx].front().second ] = r;
			v[bestIdx].pop_front();
		} else {
			answer[bestIdx][ v[bestIdx].back().second ] = r;
			v[bestIdx].pop_back();
		}

		ans2 += best;
	}

	allocate_tickets(answer);

	vector<vector<int>> rounds(k);
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			if(answer[i][j] != -1)
				rounds[answer[i][j]].push_back(x[i][j]);
	int ans = 0;
	for(int i = 0; i < k; i++) {
		ans += calcScore(rounds[i]);
	}

	if(ans2 != ans) {
		exit(-1);
	}

	return ans;
}

Compilation message

tickets.cpp: In function 'long long int solve(long long int, bool)':
tickets.cpp:65:27: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   65 |   if(usedLower.size() * 2 >= n) break;
      |      ~~~~~~~~~~~~~~~~~~~~~^~~~
tickets.cpp:66:27: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   66 |   if(usedUpper.size() * 2 >= n) break;
      |      ~~~~~~~~~~~~~~~~~~~~~^~~~
tickets.cpp:91:26: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   91 |  if(usedLower.size() * 2 > n || usedUpper.size() * 2 > n) return -1;
      |     ~~~~~~~~~~~~~~~~~~~~~^~~
tickets.cpp:91:54: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   91 |  if(usedLower.size() * 2 > n || usedUpper.size() * 2 > n) return -1;
      |                                 ~~~~~~~~~~~~~~~~~~~~~^~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 4 ms 640 KB Output is correct
6 Correct 82 ms 1784 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 4 ms 640 KB Output is correct
5 Correct 45 ms 3960 KB Output is correct
6 Correct 1207 ms 88696 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Contestant returned 5 while correct return value is 6.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB Contestant returned 11 while correct return value is 13.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB Contestant returned 11 while correct return value is 13.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB Contestant returned 11 while correct return value is 13.
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 4 ms 640 KB Output is correct
6 Correct 82 ms 1784 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 4 ms 640 KB Output is correct
11 Correct 45 ms 3960 KB Output is correct
12 Correct 1207 ms 88696 KB Output is correct
13 Incorrect 1 ms 384 KB Contestant returned 5 while correct return value is 6.
14 Halted 0 ms 0 KB -