Submission #723886

#	Time	Username	Problem	Language	Result	Execution time	Memory
723886		NemanjaSo2005	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	790 ms	97100 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;
vector<int> p[1505],m[1505];
int niz[1505];
bool cmp(int a,int b){
   return p[a].size()<p[b].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]=i;
      for(int j=0;j<M;j++){
         if(kako[i][j]==0)
            continue;
         if(kako[i][j]==1)
            p[niz[i]].push_back(j);
         else
            m[niz[i]].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]][m[niz[i]].back()]=it;
         m[niz[i]].pop_back();
      }
      for(int i=N/2;i<N;i++){
         kako[niz[i]][p[niz[i]].back()]=it;
         p[niz[i]].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:31:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |    for(int i=0;i<kako.size();i++)
      |                ~^~~~~~~~~~~~
tickets.cpp:32:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |       for(int j=0;j<kako[i].size();j++)
      |                   ~^~~~~~~~~~~~~~~
tickets.cpp:66:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |    for(int i=0;i<kako.size();i++)
      |                ~^~~~~~~~~~~~
tickets.cpp:67:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |       for(int j=0;j<kako[i].size();j++)
      |                   ~^~~~~~~~~~~~~~~

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