제출 #841467

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
841467		model_code	추월 (IOI23_overtaking)	C++17	100 / 100	598 ms	92220 KiB

overtaking

// correct/GA_full_binaryTree.cpp

#include "overtaking.h"
#include <algorithm>

using namespace std;
using ll = long long;

struct iv
{
    ll start;
    ll end;
    ll dest;
};

vector<iv> merge_intervals(const vector<iv> &iv1, const vector<iv> &iv2)
{
    vector<iv> result;
    int i = 0;
    for (int j = 0; j < iv2.size(); j++)
    {
        while (i < iv1.size() && iv1[i].dest <= iv2[j].start)
        {
            result.push_back(iv1[i]);
            i++;
        }
        ll start = iv2[j].start;
        if (i < iv1.size() && iv1[i].start <= start)
        {
            if (iv1[i].dest > iv2[j].end)
                continue;
            start = iv1[i].start;
        }
        while (i < iv1.size() && iv1[i].dest <= iv2[j].end)
        {
            i++;
        }
        ll end = iv2[j].end;
        if (i < iv1.size() && iv1[i].start <= end)
        {
            end = iv1[i].start;
        }
        result.push_back({start, end, iv2[j].dest});
    }
    while (i < iv1.size())
    {
        result.push_back(iv1[i]);
        i++;
    }
    return result;
}

vector<vector<iv>> intervals;

void merge_top()
{
    vector<iv> iv2 = intervals.back();
    intervals.pop_back();
    vector<iv> iv1 = intervals.back();
    intervals.pop_back();
    intervals.push_back(merge_intervals(iv1, iv2));
}

ll total_time;

void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
    total_time = L * (ll)X;
    vector<pair<ll, int>> initial(N);
    for (int i = 0; i < N; i++)
    {
        if (W[i] > X)
        {
            initial.emplace_back(T[i], W[i] - X);
        }
    }
    N = initial.size();
    sort(initial.begin(), initial.end());
    vector<vector<ll>> bus_time(M, vector<ll>(N));
    vector<vector<int>> bus_rv(M, vector<int>(N));
    for (int j = 0; j < N; j++)
    {
        bus_time[0][j] = initial[j].first;
        bus_rv[0][j] = initial[j].second;
    }
    for (int i = 1; i < M; i++)
    {
        ll dist = S[i] - S[i - 1];
        ll m = 0;
        for (int j = 0; j < N; j++)
        {
            int rv = bus_rv[i - 1][j];
            ll t = bus_time[i - 1][j] + rv * dist;
            if (t <= m)
            {
                bus_time[i][j] = m;
                int k = j;
                while (k >= 1 && bus_time[i][k - 1] == m && bus_rv[i][k - 1] > rv)
                {
                    bus_rv[i][k] = bus_rv[i][k - 1];
                    k--;
                }
                bus_rv[i][k] = rv;
            }
            else
            {
                bus_time[i][j] = t;
                bus_rv[i][j] = rv;
                m = t;
            }
        }
    }
    for (int i = 1; i < M; i++)
    {
        vector<iv> intervals2;
        ll last_end = 0;
        for (int j = 0; j < N; j++)
        {
            if (bus_time[i][j] > last_end)
            {
                if (bus_time[i - 1][j] < last_end)
                {
                    intervals2.back().end = bus_time[i - 1][j];
                }
                intervals2.push_back(
                    {bus_time[i - 1][j], bus_time[i][j], bus_time[i][j]});
                last_end = bus_time[i][j];
            }
        }
        intervals.push_back(move(intervals2));
        for (int j = 1; j < 12; j++)
        {
            if (!(i & (1 << j) - 1))
            {
                merge_top();
            }
        }
    }
    while (intervals.size() > 1)
    {
        merge_top();
    }
}

long long arrival_time(long long Y)
{
    vector<iv> &iv = intervals[0];
    int l = -1;
    int u = iv.size();
    while (l + 1 < u)
    {
        int m = (l + u) / 2;
        if (iv[m].start < Y && Y <= iv[m].end)
        {
            return iv[m].dest + total_time;
        }
        else if (Y <= iv[m].start)
        {
            u = m;
        }
        else
        {
            l = m;
        }
    }
    return Y + total_time;
}

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

overtaking.cpp: In function 'std::vector<iv> merge_intervals(const std::vector<iv>&, const std::vector<iv>&)':
overtaking.cpp:20:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<iv>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for (int j = 0; j < iv2.size(); j++)
      |                     ~~^~~~~~~~~~~~
overtaking.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<iv>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         while (i < iv1.size() && iv1[i].dest <= iv2[j].start)
      |                ~~^~~~~~~~~~~~
overtaking.cpp:28:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<iv>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         if (i < iv1.size() && iv1[i].start <= start)
      |             ~~^~~~~~~~~~~~
overtaking.cpp:34:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<iv>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         while (i < iv1.size() && iv1[i].dest <= iv2[j].end)
      |                ~~^~~~~~~~~~~~
overtaking.cpp:39:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<iv>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         if (i < iv1.size() && iv1[i].start <= end)
      |             ~~^~~~~~~~~~~~
overtaking.cpp:45:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<iv>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     while (i < iv1.size())
      |            ~~^~~~~~~~~~~~
overtaking.cpp: In function 'void init(int, int, std::vector<long long int>, std::vector<int>, int, int, std::vector<int>)':
overtaking.cpp:133:32: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
  133 |             if (!(i & (1 << j) - 1))
      |                       ~~~~~~~~~^~~

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