oj.uz

답안 #613968

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
613968 2022-07-30T15:05:40 Z Mounir 카니발 티켓 (IOI20_tickets) C++14
27 / 100
 688 ms 55716 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);
		set<int> vals;
		for (int i = 0; i < nCouleurs; ++i)
		{
			options[i] = {x[i][left[i]], x[i][right[i]]};
			vals.insert(x[i][0]);
			vals.insert(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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 57 ms 836 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 31 ms 2328 KB Output is correct
6 Correct 688 ms 51384 KB Output is correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 19 ms 2388 KB Output is correct
6 Correct 498 ms 52344 KB Output is correct
7 Correct 513 ms 55716 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Incorrect 1 ms 212 KB Contestant returned 43 while correct return value is 45.
11 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 57 ms 836 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 31 ms 2328 KB Output is correct
12 Correct 688 ms 51384 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 2 ms 340 KB Output is correct
17 Correct 19 ms 2388 KB Output is correct
18 Correct 498 ms 52344 KB Output is correct
19 Correct 513 ms 55716 KB Output is correct
20 Correct 3 ms 468 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Incorrect 1 ms 212 KB Contestant returned 43 while correct return value is 45.
23 Halted 0 ms 0 KB -