This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "tickets.h"
#include<bits/stdc++.h>
using namespace std;
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n=x.size();
int m=x[0].size();
vector<vector<int> > answer(n, vector<int> (m, -1));
long long ans=0;
vector<pair<int, pair<int,int> > > sorted;
vector<set<pair<int,int> > > smaller(k);
for(int i=0; i<n; i++){
for(int j=0; j<k; j++){
ans-=x[i][j];
sorted.push_back({x[i][j]+x[i][m-1-j], {i, j}});
answer[i][j]=j;
smaller[j].insert({i, j});
}
}
sort(sorted.begin(), sorted.end());
vector<set<pair<int,int> > > bigger(k);
for(int i=0; i<(n*k)/2; i++){
int gain=sorted[i].first;
auto [ind, j]=sorted[i].second;
ans += gain;
smaller[j].erase({ind, j});
bigger[j].insert({ind, j});
}
vector<int> manybig;
vector<int> manysmall;
for(int i=0; i<k; i++){
if(bigger[i].size()>(n/2)){
manybig.push_back(i);
}
else if(bigger[i].size()<(n/2)){
manysmall.push_back(i);
}
}
int mom=0;
for(auto i: manybig){
int cnt=0;
while(bigger[i].size()-cnt > (n/2)){
vector<pair<int,int> > gone;
int inds=manysmall[mom];
for(auto [ind, j]: bigger[i]){
if(bigger[i].size()-cnt==(n/2)) break;
auto it=smaller[inds].lower_bound({ind, 0});
if(it!=smaller[inds].end() && (*it).first==ind){
swap(answer[ind][j], answer[ind][(*it).second]);
smaller[inds].erase(*it);
gone.push_back({ind, j});
cnt++;
}
if(smaller[manysmall[mom]].size()==(n/2)){
mom++;
break;
}
}
for(auto e: gone){
bigger[i].erase(e);
}
cnt=0;
}
}
allocate_tickets(answer);
return ans;
}
/*signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m, k;
cin >> n >> m >> k;
vector<vector<int> > x(n, vector<int> (m));
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
cin >> x[i][j];
}
}
cout <<
}*/
Compilation message (stderr)
tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:37:28: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
37 | if(bigger[i].size()>(n/2)){
| ~~~~~~~~~~~~~~~~^~~~~~
tickets.cpp:40:33: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
40 | else if(bigger[i].size()<(n/2)){
| ~~~~~~~~~~~~~~~~^~~~~~
tickets.cpp:49:36: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
49 | while(bigger[i].size()-cnt > (n/2)){
| ~~~~~~~~~~~~~~~~~~~~~^~~~~~~
tickets.cpp:55:40: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
55 | if(bigger[i].size()-cnt==(n/2)) break;
| ~~~~~~~~~~~~~~~~~~~~^~~~~~~
tickets.cpp:67:50: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
67 | if(smaller[manysmall[mom]].size()==(n/2)){
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |