oj.uz

Submission #753225

# Submission time Handle Problem Language Result Execution time Memory
753225 2023-06-04T21:36:02 Z tolbi Carnival Tickets (IOI20_tickets) C++17
25 / 100
 624 ms 68252 KB 
#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz...
//Sani buyuk Osman Pasa Plevneden cikmam diyor.
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulhamidHan
#define author tolbi
#include <bits/stdc++.h>
using namespace std;
template<typename X, typename Y> istream& operator>>(istream& in, pair<X,Y> &pr) {return in>>pr.first>>pr.second;}
template<typename X, typename Y> ostream& operator<<(ostream& os, pair<X,Y> pr) {return os<<pr.first<<" "<<pr.second;}
template<typename X> istream& operator>>(istream& in, vector<X> &arr) {for(auto &it : arr) in>>it; return in;}
template<typename X> ostream& operator<<(ostream& os, vector<X> arr) {for(auto &it : arr) os<<it<<" "; return os;}
template<typename X, size_t Y> istream& operator>>(istream& in, array<X,Y> &arr) {for(auto &it : arr) in>>it; return in;}
template<typename X, size_t Y> ostream& operator<<(ostream& os, array<X,Y> arr) {for(auto &it : arr) os<<it<<" "; return os;}
#define endl '\n'
#define vint(x) vector<int> x
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define cinarr(x) for (auto &it : x) cin>>it;
#define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl;
#define sortarr(x) sort(x.begin(),x.end())
#define sortrarr(x) sort(x.rbegin(),x.rend())
#define det(x) cout<<"NO\0YES"+x*3<<endl;
#define INF LONG_LONG_MAX
#define rev(x) reverse(x.begin(),x.end());
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define tol(bi) (1LL<<((int)(bi)))
const int MOD = 1e9+7;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
#include "tickets.h"

long long find_maximum(int32_t k, vector<vector<int32_t>> x) {
	if (x[0].size()!=1){
		int n = x.size();
		int m = x[0].size();
		vector<vector<int32_t>> rval(n,vector<int32_t>(m,-1));
		vector<vector<int>> ones(n);
		vector<vector<int>> zeros(n);
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < m; j++){
				if (x[i][j]==0) zeros[i].push_back(j);
				else ones[i].push_back(j);
			}
		}
		int tur = 0;
		int ans = 0;
		while (tur<k){
			int zor = n/2;
			bool ist = n%2;
			priority_queue<pair<int,int>> pq;
			for (int i = 0; i < n; ++i)
			{
				pq.push({ones[i].size()-zeros[i].size(),i});
			}
			int a = 0;
			int b = 0;
			while (pq.size()){
				int node = pq.top().second;
				pq.pop();
				if (zor>0){
					zor--;
					if (ones[node].size()){
						a++;
						rval[node][ones[node].back()]=tur;
						ones[node].pop_back();
					}
					else {
						b++;
						rval[node][zeros[node].back()]=tur;
						zeros[node].pop_back();
					}
				}
				else if (ist){
					ist = false;
					if (ones[node].size()>=zeros[node].size()){
						a++;
						rval[node][ones[node].back()]=tur;
						ones[node].pop_back();
					}
					else {
						b++;
						rval[node][zeros[node].back()]=tur;
						zeros[node].pop_back();
					}
				}
				else {
					if (zeros[node].size()){
						b++;
						rval[node][zeros[node].back()]=tur;
						zeros[node].pop_back();
					}
					else {
						a++;
						rval[node][ones[node].back()]=tur;
						ones[node].pop_back();
					}
				}
			}
			ans+=min(a,b);
			tur++;
		}
		allocate_tickets(rval);
		return ans;
	}
	else {
		int32_t n = x.size();
		int32_t m = x[0].size();
		vector<vector<int32_t>> answer;
		for (int32_t i = 0; i < n; i++) {
			vector<int32_t> row(m);
			for (int32_t j = 0; j < m; j++) {
				if (j < k) {
					row[j] = j;
				} else {
					row[j] = -1;
				}
			}
			answer.push_back(row);
		}
		for (int i = 0; i < n; i++){
			for (int j = 0; j < m; j++){
				answer[i][j]=0;
			}
		}
		allocate_tickets(answer);
		vector<long long> arr;
		for (int i = 0; i < n; ++i)
		{
			arr.push_back(x[i][0]);
		}
		sortarr(arr);
		long long ans = 0;
		for (int i = 0; i < n; i++){
			ans+=abs(arr[i]-arr[arr.size()/2]);
		}
		return ans;
	}
}

Compilation message

tickets.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 | #pragma optimize("Bismillahirrahmanirrahim")
      |

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 300 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 2 ms 724 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Contestant returned 803235448 but the tickets gives a total value of 0
2 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory 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 468 KB Output is correct
5 Correct 20 ms 2988 KB Output is correct
6 Correct 506 ms 64508 KB Output is correct
7 Correct 579 ms 64972 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 6 ms 852 KB Output is correct
13 Correct 19 ms 2388 KB Output is correct
14 Correct 17 ms 2344 KB Output is correct
15 Correct 624 ms 68252 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Contestant returned 11 but the tickets gives a total value of 3
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 but the tickets gives a total value of 3
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 but the tickets gives a total value of 3
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 300 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Incorrect 0 ms 212 KB Contestant returned 803235448 but the tickets gives a total value of 0
8 Halted 0 ms 0 KB -