Submission #1046376

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046376		n1k	Carnival Tickets (IOI20_tickets)	C++17	11 / 100	1 ms	860 KiB

tickets

#include "tickets.h"
#include <vector>

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}

//#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#define debug(...) 0

int n, m;

ll get(vector<int> v){
	sort(v.begin(), v.end());
	ll t = 0;	
	for(int i=0; i<v.size(); i++) t += abs(v[i] - v[v.size()/2]);
	return t;
}

tuple<ll, vector<vector<int>>> calc(vector<array<ll, 2>> v){
	vector<std::vector<int>> ans(n, vector<int>(m, -1));
	ll t = 0;
	set<int> s;
	for(int i=0; i<v.size(); i++){
		auto [x, id] = v[i];
		if(not s.count(id)){
			t -= x;
			ans[id][0] = 0;
		}
		s.insert(id);

		if(s.size()==n/2){
			ll add = 0;
			for(int j=v.size()-1; j>i; j--){
				if(s.count(v[j].back())){
					continue;
				}
				s.insert(v[j].back());
				add += v[j].front();
				ans[v[j].back()][m-1] = 0;
			}
			return make_tuple(t + add, ans);
		}
	}
}

long long find_maximum(int k, std::vector<std::vector<int>> x) {
	n = x.size();
	m = x[0].size();

	std::vector<std::vector<int>> answer(n, vector<int>(m));
	vector<array<ll, 2>> v;
	for(int i=0; i<n; i++){
		v.push_back({x[i].front(), i});
		v.push_back({x[i].back(), i});
	}

	sort(v.begin(), v.end());

	debug(v);

	auto [cost1, ans1] = calc(v);	
	reverse(v.begin(), v.end());
	auto [cost2, ans2] = calc(v);

	cost2 = abs(cost2);
	if(cost1<cost2){
		swap(cost1, cost2);
		swap(ans1, ans2);
	}

	allocate_tickets(ans1);
	return cost1;
}

Compilation message (stderr)

tickets.cpp: In function 'll get(std::vector<int>)':
tickets.cpp:40:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for(int i=0; i<v.size(); i++) t += abs(v[i] - v[v.size()/2]);
      |               ~^~~~~~~~~
tickets.cpp: In function 'std::tuple<long long int, std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > > calc(std::vector<std::array<long long int, 2> >)':
tickets.cpp:48:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for(int i=0; i<v.size(); i++){
      |               ~^~~~~~~~~
tickets.cpp:56:14: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   56 |   if(s.size()==n/2){
      |      ~~~~~~~~^~~~~
tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:33:20: warning: statement has no effect [-Wunused-value]
   33 | #define debug(...) 0
      |                    ^
tickets.cpp:84:2: note: in expansion of macro 'debug'
   84 |  debug(v);
      |  ^~~~~
tickets.cpp: In function 'std::tuple<long long int, std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > > calc(std::vector<std::array<long long int, 2> >)':
tickets.cpp:45:52: warning: control reaches end of non-void function [-Wreturn-type]
   45 |  vector<std::vector<int>> ans(n, vector<int>(m, -1));
      |                                                    ^

• Subtask 1: 11 / 11
• Subtask 2: 0 / 16
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23
• Subtask 7: 0 / 10