| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 723882 | NemanjaSo2005 | Carnival Tickets (IOI20_tickets) | C++14 | 0 ms | 0 KiB |
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<bits/stdc++.h>
#include "tickets.h"
#define ll long long
using namespace std;
ll N,M,K,vred=0,pok[1505];
vector<vector<int>> kako,koliko;
struct slog{
int gde;
ll dob;
bool operator < (const slog &a) const{
return dob<a.dob;
}
}pp;
struct boja{
vector<int> p,m;
int ind;
} niz[1505];
bool cmp(boja a,boja b){
return a.p.size()<b.p.size();
}
priority_queue<slog> PQ;
void stavi(int gde){
if(pok[gde]<0)
return;
pp.gde=gde;
pp.dob=koliko[gde][pok[gde]]+koliko[gde][pok[gde]+M-K];
PQ.push(pp);
return;
}
ll find_maximum(int k,vector<vector<int>> d){
kako=d;
koliko=d;
for(int i=0;i<kako.size();i++)
for(int j=0;j<kako[i].size();j++)
kako[i][j]=0;
K=k;
N=d.size();
M=d[0].size();
for(int i=0;i<N;i++){
pok[i]=K-1;
for(int j=0;j<K;j++){
kako[i][j]=-1;
vred-=koliko[i][j];
}
stavi(i);
}
for(int it=1;it<=N*K/2;it++){
int gde=PQ.top().gde;
// cout<<gde<<" "<<pok[gde]<<endl;
vred+=PQ.top().dob;
PQ.pop();
kako[gde][pok[gde]]=0;
kako[gde][pok[gde]+M-K]=1;
pok[gde]--;
stavi(gde);
}
for(int i=0;i<N;i++){
niz[i].ind=i;
for(int j=0;j<M;j++){
if(kako[i][j]==0)
continue;
if(kako[i][j]==1)
niz[i].p.push_back(j);
else
niz[i].m.push_back(j);
}
}
for(int i=0;i<kako.size();i++)
for(int j=0;j<kako[i].size();j++)
kako[i][j]=-1;
for(int it=0;it<K;it++){
// cout<<it<<endl;
sort(niz,niz+N,cmp);
//for(int i=0;i<N;i++)
// cout<<niz[i].m.size()<<" "<<niz[i].p.size()<<endl;
for(int i=0;i<N/2;i++){
kako[niz[i].ind][niz[i].m.back()]=it;
niz[i].m.pop_back();
}
for(int i=N/2;i<N;i++){
kako[niz[i].ind][niz[i].p.back()]=it;
niz[i].p.pop_back();
}
}
allocate_tickets(kako);
return vred;
}
#include "tickets.h"
#include <cassert>
#include <cstdio>
#include <vector>
#include <string>
static int n;
static int m;
static int k;
static std::vector<std::vector<int>> d;
static std::vector<std::vector<int>> x;
static int called = 0;
static void check(bool cond, std::string message) {
if (!cond) {
printf("%s\n", message.c_str());
exit(0);
}
}
void allocate_tickets( std::vector<std::vector<int>> _d) {
check(!called, "allocate_tickets called more than once");
d = _d;
check((int)d.size() == n, "allocate_tickets called with parameter of wrong size");
for (int i = 0; i < n; i++) {
check((int)d[i].size() == m, "allocate_tickets called with parameter of wrong size");
}
called = 1;
}
int main() {
assert(scanf("%d %d %d", &n, &m, &k) == 3);
x.resize(n);
for (int i = 0; i < n; i++) {
x[i].resize(m);
for (int j=0; j < m; j++) {
assert(scanf("%d", &x[i][j]) == 1);
}
}
fclose(stdin);
long long answer = find_maximum(k, x);
check(called, "failure to call allocate_tickets");
printf("%lld\n", answer);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (j) printf(" ");
printf("%d", d[i][j]);
}
printf("\n");
}
fclose(stdout);
return 0;
}