oj.uz

Submission #613967

# Submission time Handle Problem Language Result Execution time Memory
613967 2022-07-30T15:04:37 Z Mounir Carnival Tickets (IOI20_tickets) C++14
27 / 100
 3000 ms 51724 KB 
#include "tickets.h"
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define chmax(x, v) x = max(x, v)
#define chmin(x, v) x = min(x, v)
#define pb push_back
#define pii pair<int, int>
#define sz(x) (int)x.size()
#define x first
#define y second
#define int long long
using namespace std;
 
struct Move
{
	int id;
	int perte;
 
	bool operator<(const Move &autre) const
	{
		if (perte != autre.perte)
			return perte < autre.perte;
		return id < autre.id;
	}
};
 
const long long OO = 1e14;
 
long long find_maximum(signed k, vector<vector<signed>> x)
{
	int nCouleurs = sz(x);
	int TOTAL = 0;
	vector<vector<signed>> ans;
	ans.resize(nCouleurs);
	for (auto& ligne : ans){
		ligne.resize(sz(x[0]));
		for (auto& val : ligne)
			val = -1;
	}

	vector<int> left(nCouleurs, 0), right(nCouleurs, sz(x[0]) - 1);
	// On suppose k = 1
	for (int i = 0; i < k; ++i){
		vector<pii> options(nCouleurs);
		vector<int> vals;
		for (int i = 0; i < nCouleurs; ++i)
		{
			options[i] = {x[i][left[i]], x[i][right[i]]};
			vals.pb(x[i][0]);
			vals.pb(x[i][sz(x[0]) - 1]);
		}
 
		vector<int> utilises;
		int gain = 0;
		sort(all(vals));
		for (int med : vals) {
			vector<Move> moves;
			int tot = 0, enDessous = 0;
			vector<int> left(nCouleurs, 0);
			for (int id = 0; id < nCouleurs; ++id) {
				int perte = 0;
				tot += abs(med - options[id].x);
				enDessous += (options[id].y < med);
				if (options[id].y < med)
					left[id] = 1;
				if (options[id].y < med || options[id].x > med)
					perte = OO;
				else {
					perte = abs(options[id].x - med) - abs(options[id].y - med);
					enDessous++;
					left[id] = 1;
				}
				moves.pb({id, perte});
			}
 
		//cout << tot << endl;
			sort(all(moves));
			int i;
			for (i = 0; enDessous > nCouleurs/2; ++i, --enDessous){
				tot -= moves[i].perte;
				left[moves[i].id] = 0;
			}
 
//if (enDessous >= nCouleurs/2)
//			continue;
/*
		cout << "med" << med << " " << tot << " " << enDessous << endl;
		for (int i : left)
			cout << i << " ";
		cout << endl;*/
			if (tot > gain && enDessous == nCouleurs/2){
				gain = tot;
				utilises = left;
			}
		}
		TOTAL += gain;
		for (int ilig = 0; ilig < nCouleurs; ++ilig){
			if (utilises[ilig])
				ans[ilig][left[ilig]++] = i;
			else
				ans[ilig][right[ilig]--] = i;
		}
	}

/*	for (int utilise : utilises)
		cout << utilise << " ";
	cout << endl;
*/
 
	allocate_tickets(ans);
	return TOTAL;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 296 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 5 ms 340 KB Output is correct
6 Correct 103 ms 712 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 31 ms 3172 KB Output is correct
6 Correct 729 ms 51724 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 13 ms 404 KB Output is correct
5 Correct 663 ms 2604 KB Output is correct
6 Execution timed out 3015 ms 30200 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 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 0 ms 212 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 0 ms 212 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 212 KB Output is correct
2 Correct 0 ms 296 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 5 ms 340 KB Output is correct
6 Correct 103 ms 712 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 31 ms 3172 KB Output is correct
12 Correct 729 ms 51724 KB Output is correct
13 Correct 1 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 13 ms 404 KB Output is correct
17 Correct 663 ms 2604 KB Output is correct
18 Execution timed out 3015 ms 30200 KB Time limit exceeded
19 Halted 0 ms 0 KB -