제출 #858876

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
858876		superMOOZ	추월 (IOI23_overtaking)	C++17	65 / 100	3573 ms	56748 KiB

overtaking

#include "overtaking.h"

#include <vector>
#include <set>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;

int L, N, X, M;
vector<long long> T;
vector<int> W, S;


pair<long long, int> arrival_vec[1005][1005];  // [stop][rank] = {time, id}
long long arrival_t[1005][1005];  // [stop][id]

vector<pair<long long, long long>> info[1005];  // sorted - [stop][..] = {from time, earliest arrival}

void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
    ::L = L;
    ::N = N;
    ::T = T;
    ::W = W;
    ::X = X;
    ::M = M;
    ::S = S;
    for (int i=0; i<N; ++i) {
        arrival_vec[0][i] = {T[i], i};
        arrival_t[0][i] = T[i];
    }
    sort(arrival_vec[0], arrival_vec[0] + N);
    for (int stop=1; stop<M; ++stop) {
        long long earliest_arrival = 0;
        long long staging_earliest_arrival = 0;
        for (int i=0; i<N; ++i) {
            int id = arrival_vec[stop-1][i].second;
            long long arrival = arrival_t[stop-1][id] + 1LL*(S[stop]-S[stop-1])*W[id];
            arrival = max(arrival, earliest_arrival);
            arrival_vec[stop][i] = {arrival, id};
            arrival_t[stop][id] = arrival;
            staging_earliest_arrival = max(arrival, staging_earliest_arrival);
            if (i < N-1 && arrival_vec[stop-1][i+1].first == arrival_vec[stop-1][i].first) continue;
            earliest_arrival = staging_earliest_arrival;
        }
        sort(arrival_vec[stop], arrival_vec[stop] + N);
    }
    // Preprocessing
    vector<pair<long long, long long>> tmap[1005];  // [stop] = {{time, earliest arrival}, ...}
    for (int stop=1; stop<M; ++stop) {
        for (auto p : arrival_vec[stop]) {
            long long arrival = p.first;
            int id = p.second;
            long long prev_from = p.first - 1LL*(S[stop]-S[stop-1])*W[id];
            tmap[stop-1].push_back({prev_from + 1, arrival});
        }
    }
    for (int stop=0; stop<M-1; ++stop) {
        sort(tmap[stop].begin(), tmap[stop].end());
        long long max_blocker = 0;
        for (int i=0; i<tmap[stop].size(); ++i) {
            const auto& p = tmap[stop][i];
            long long time = p.first;
            long long earliest_arrival = p.second;
            max_blocker = max(max_blocker, earliest_arrival);
            if (i != tmap[stop].size()-1 && tmap[stop][i].first == tmap[stop][i+1].first) continue;
            info[stop].push_back({time, max_blocker});
        }
    }
    return;
}

long long arrival_time(long long Y)
{
    for (int stop=0; stop<M-1; ++stop) {
        int l=0, r=(int)info[stop].size() - 1;
        int res = -1;
        while (l<=r)  {
            int mid = (l+r)/2;
            if (info[stop][mid].first > Y) r = mid-1;
            else {
                res = mid;
                l = mid+1;
            }
        }
        long long earliest_arrival = 0;
        if (res != -1) earliest_arrival = info[stop][res].second;
        Y = max(earliest_arrival, Y + 1LL*(S[stop+1]-S[stop])*X);
    }
    return Y;
}

컴파일 시 표준 에러 (stderr) 메시지

overtaking.cpp: In function 'void init(int, int, std::vector<long long int>, std::vector<int>, int, int, std::vector<int>)':
overtaking.cpp:62:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         for (int i=0; i<tmap[stop].size(); ++i) {
      |                       ~^~~~~~~~~~~~~~~~~~
overtaking.cpp:67:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |             if (i != tmap[stop].size()-1 && tmap[stop][i].first == tmap[stop][i+1].first) continue;
      |                 ~~^~~~~~~~~~~~~~~~~~~~~~

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