Submission #1058141

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058141		TheQuantiX	Overtaking (IOI23_overtaking)	C++17	39 / 100	3528 ms	600 KiB

overtaking

#include <bits/stdc++.h>
#include "overtaking.h"

using namespace std;
using ll = long long;

ll n, m, q, k, x, y, a, b, c, l;
vector<ll> t;
vector<int> w, s;

void init(int L, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S) {
    n = N;
    m = M;
    l = L;
    x = X;
    t = T;
    w = W;
    s = S;
}

long long arrival_time(long long Y) {
    vector< pair<ll, ll> > v;
    for (int i = 0; i < n; i++) {
        if (t[i] != Y) {
            v.push_back({t[i], i});
        }
    }
    v.push_back({Y, n});
    for (int i = 1; i < m; i++) {
        sort(v.begin(), v.end());
        // for (auto j : v) {
        //     cout << j.first << ' ' << j.second << "  ";
        // }
        // cout << '\n';
        vector< pair<ll, ll> > e;
        ll mx = 0;
        ll num = 0;
        for (int j = 0; j < v.size(); j++) {
            vector< pair<ll, ll> > e2;
            ll x1 = v[j].first;
            while (v[j].first == x1) {
                e2.push_back({v[j].first + (v[j].second == n ? x : w[v[j].second]) * (s[i] - s[i - 1]), v[j].second});
                j++;
            }
            for (auto &i : e2) {
                i.first = max(mx, i.first);
                if (i.second == n) {
                    num = i.first;
                }
            }
            for (auto &i : e2) {
                mx = max(i.first, mx);
                e.push_back(i);
            }
            j--;
        }
        v.clear();
        for (auto j : e) {
            if (j.second == n || j.first != num) {
                v.push_back(j);
            }
        }
    }
    // cout << '\n';
    for (auto i : v) {
        if (i.second == n) {
            return i.first;
        }
    }
}

Compilation message (stderr)

overtaking.cpp: In function 'long long int arrival_time(long long int)':
overtaking.cpp:38:27: 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]
   38 |         for (int j = 0; j < v.size(); j++) {
      |                         ~~^~~~~~~~~~
overtaking.cpp:22:28: warning: control reaches end of non-void function [-Wreturn-type]
   22 |     vector< pair<ll, ll> > v;
      |                            ^

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