Submission #1061389

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061389		tolbi	Overtaking (IOI23_overtaking)	C++17	65 / 100	3554 ms	34124 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<vector<array<int,3>>> bus;
vector<vector<int>> hsh;
vector<int> S;
int X;
void init(int32_t L, int32_t N, std::vector<long long> T, std::vector<int32_t> W, int32_t X, int32_t M, std::vector<int32_t> S)
{
    ::X=X;
    ::S.resize(S.size());
    for (int i = 0; i < S.size(); i++) ::S[i]=S[i];
        bus.push_back(vector<array<int,3>>());
    hsh.push_back(vector<int>(N));
    for (int i = 0; i < N; i++){
        bus.back().push_back({T[i],W[i],i});
    }
    sort(bus.back().begin(), bus.back().end());
    for (int i = 1; i < M; i++){
        bus.push_back(bus.back());
        int pmax = 0;
        for (int j = 0; j < N; j++){
            bus.back()[j][0]+=bus.back()[j][1]*(::S[i]-::S[i-1]);
            pmax=max(pmax,bus.back()[j][0]);
            bus.back()[j][0]=pmax;
        }
        sort(bus.back().begin(), bus.back().end());
        for (int j = 0; j < bus.back().size(); j++){
            hsh.back()[bus.back()[j][2]]=j;
        }
        if (i!=M-1){
            hsh.push_back(hsh.back());
        }
    }
}

int arrival_time(int Y)
{
    pair<int,int> bne = {Y,X};
    for (int i = 0; i < S.size()-1; i++){
        int bendenkuc = -1;
        auto it = lower_bound(bus[i].begin(), bus[i].end(), array<int,3>{bne.first,0,0});
        if (it!=bus[i].begin()){
            it--;
            bendenkuc = hsh[i][(*it)[2]];
        }
        if (bendenkuc==-1){
            bne.first+=bne.second*(S[i+1]-S[i]);
        }
        else {
            bne.first=max(bne.first+bne.second*(S[i+1]-S[i]),bus[i+1][bendenkuc][0]);            
        }
    }
    return bne.first;
}

Compilation message (stderr)

overtaking.cpp: In function 'void init(int32_t, int32_t, std::vector<long long int>, std::vector<int>, int32_t, int32_t, std::vector<int>)':
overtaking.cpp:13:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for (int i = 0; i < S.size(); i++) ::S[i]=S[i];
      |                     ~~^~~~~~~~~~
overtaking.cpp:29:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         for (int j = 0; j < bus.back().size(); j++){
      |                         ~~^~~~~~~~~~~~~~~~~~~
overtaking.cpp: In function 'long long int arrival_time(long long int)':
overtaking.cpp:41:23: 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]
   41 |     for (int i = 0; i < S.size()-1; i++){
      |                     ~~^~~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 26 / 26
• Subtask 5: 0 / 35