Submission #723883

#	Time	Username	Problem	Language	Result	Execution time	Memory
723883		NemanjaSo2005	Carnival Tickets (IOI20_tickets)	C++14	62 / 100	3073 ms	71808 KiB

tickets

#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;
}

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:33:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |    for(int i=0;i<kako.size();i++)
      |                ~^~~~~~~~~~~~
tickets.cpp:34:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |       for(int j=0;j<kako[i].size();j++)
      |                   ~^~~~~~~~~~~~~~~
tickets.cpp:68:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |    for(int i=0;i<kako.size();i++)
      |                ~^~~~~~~~~~~~
tickets.cpp:69:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |       for(int j=0;j<kako[i].size();j++)
      |                   ~^~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 16 / 16
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23
• Subtask 7: 0 / 10