Submission #579285

#TimeUsernameProblemLanguageResultExecution timeMemory
579285AugustinasJucasCarnival Tickets (IOI20_tickets)C++14
27 / 100
583 ms60652 KiB
#include <bits/stdc++.h> #include "tickets.h" using namespace std; vector<vector<int> > mas, ans; vector<vector<pair<int, int> > > maz, did, pos; long long find_maximum(int k, vector<vector<int> > x) { int n = x.size(); int m = x[0].size(); mas = ans = x; for(auto &x : ans) for(auto &y : x) y = -1; maz.resize(n); did.resize(n); pos.resize(n); long long sum = 0; priority_queue<pair<long long, int> > q; for(int i = 0; i < n; i++) { vector<pair<int, int> > dd, mm; for(int j = 0; j < m; j++) { dd.push_back({x[i][j], j}); mm.push_back({x[i][j], j}); } sort(mm.begin(), mm.end()); sort(dd.begin(), dd.end()); reverse(dd.begin(), dd.end()); for(int j = 0; j < k; j++) { sum -= mm[j].first; maz[i].push_back(mm[j]); pos[i].push_back(dd[j]); } reverse(pos[i].begin(), pos[i].end()); q.push({pos[i].back().first + maz[i].back().first, i}); } for(int i = 0; i < n * k / 2; i++) { long long pl = q.top().first; int ind = q.top().second; q.pop(); sum += pl; maz[ind].pop_back(); did[ind].push_back(pos[ind].back()); pos[ind].pop_back(); if(pos[ind].size()) { q.push({pos[ind].back().first + maz[ind].back().first, ind}); } } /* for(int i = 0; i < n; i++) { for(auto &x : maz[i]) ans[] } */ vector<int> bal (m, 0); // cout << "start" << endl; for(int i = 0; i < n; i++) { int i1 = 0; int i2 = 0; for(int j = 0; j < k; j++) { if(i1 == did[i].size()) { ans[i][maz[i][i2].second] = j; i2++; }else { if(bal[j] != n / 2) { ans[i][did[i][i1].second] = j; i1++; bal[j]++; }else { // cout << "i2 = " << i2 << ", maz[i].size() = " << maz[i].size() << endl; ans[i][maz[i][i2].second] = j; i2++; } } } } allocate_tickets(ans); return sum; /* 2 3 2 0 2 5 1 1 3 4 2 1 5 9 1 4 3 6 2 7 */ //allocate_tickets(answer); }

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:54:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |             if(i1 == did[i].size()) {
      |                ~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...