Submission #428884

#	Time	Username	Problem	Language	Result	Execution time	Memory
428884		davi_bart	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	1071 ms	154644 KiB

tickets

#include "tickets.h"
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define fi first
#define se second
#define ld long double
#define pb push_back
vector<std::vector<signed>> ans;
bool vis[2000][2000];
int presi[2000];
int N,M;
vector<int> x[2000],y[2000];
vector<int> start(2001);



vector<int> v[2000];
int val[2000][2000];

long long find_maximum(signed k, std::vector<std::vector<signed>> z) {
	N = z.size();
	M = z[0].size();


    int tot=0;
    vector<pair<int,int> > p;
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            v[i].pb(j);
        }
        sort(v[i].begin(),v[i].end(),[&](int a,int b){
            return z[i][a]>z[i][b];
        });
        int s=0;
        for(int j=0;j<k;j++)s+=z[i][v[i][j]];
        val[i][k]=s;
        tot+=s;
        for(int j=0;j<k;j++){
            s=s-z[i][v[i][k-j-1]]-z[i][v[i][v[i].size()-j-1]];
            val[i][k-j-1]=s;
        }
        for(int j=k;j>0;j--)p.pb({val[i][j]-val[i][j-1],i});
        presi[i]=k;
    }

    sort(p.begin(),p.end());
    for(int i=0;i<N*k/2;i++){
        tot-=p[i].fi;
        presi[p[i].se]--;
    }

    for(int i=0;i<N;i++){
        //cout<<"ciao: "<<i<<" "<<presi[i]<<endl;
        for(int j=0;j<presi[i];j++)x[i].pb(v[i][j]);
        for(int j=M-1;j>=M-(k-presi[i]);j--)y[i].pb(v[i][j]);
    }


	for (int i=0;i<N;i++) {
		vector<signed> row(M,-1);
        ans.pb(row);
	}

    int pos=0;
    for(int i=0;i<N;i++){
        start[i]=pos;
        for(int j=0;j<x[i].size();j++){
            ans[i][x[i][j]]=pos;
            pos=(pos+1)%k;
        }
    }
    for(int i=0;i<N;i++){
        pos=(start[i]-1+k)%k;
        for(int j=0;j<y[i].size();j++){
            ans[i][y[i][j]]=pos;
            pos=(pos-1+k)%k;
        }
    }

	allocate_tickets(ans);
	return tot;
}

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:70:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         for(int j=0;j<x[i].size();j++){
      |                     ~^~~~~~~~~~~~
tickets.cpp:77:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         for(int j=0;j<y[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