Submission #916100

#	Time	Username	Problem	Language	Result	Execution time	Memory
916100		redstonegamer22	Overtaking (IOI23_overtaking)	C++17	39 / 100	3555 ms	600 KiB

overtaking

#ifndef LOCAL
	#include "overtaking.h"
#endif // LOCAL
#ifdef LOCAL
	#include <vector>

	void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S);

	long long arrival_time(long long Y);
#endif // LOCAL

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct bus {
	int start_time;
	int speed;
};

vector<bus> glob_busses;
vector<int> stations;
int X_init;

#undef int
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S) {
#define int long long
	// scad X (viteza autobuzului de query) din fiecare viteza de autobuz (W)
	for(int i = 0; i < N; ++i) {
		W[i] -= X;
	}
	X_init = X;

	// initialize busses
	for(int i = 0; i < N; ++i) {
		bus b;
		b.start_time = T[i];
		b.speed = W[i];

		if(W[i] <= 0) continue; // acest autobuz nu afecteaza autobuzul meu!

		glob_busses.push_back(b);
	}

	// initialize stations
	for(int i = 0; i < M; ++i) {
		stations.push_back(S[i]);
	}
}

long long arrival_time_brut(long long Y) {
	auto busses = glob_busses;
	busses.push_back({Y, 0}); // autobuzul meu incepe la timpul Y si are viteza 0

	sort(busses.begin(), busses.end(), [](bus a, bus b) {
		if(a.start_time != b.start_time) 
			return a.start_time < b.start_time;
		return a.speed < b.speed;
	});

	for(int i = 0; i + 1 < stations.size(); i++) {
		int distance = stations[i + 1] - stations[i];

		int max_prefix = -1e9;

		vector<bus> new_busses;
		for(auto b : busses) {
			max_prefix = max(max_prefix, b.start_time + distance * b.speed);
			new_busses.push_back({max_prefix, b.speed});
		}

		busses = new_busses;

		sort(busses.begin(), busses.end(), [](bus a, bus b) {
			if(a.start_time != b.start_time) 
				return a.start_time < b.start_time;
			return a.speed < b.speed;
		});
	}

	for(auto b : busses) {
		if(b.speed == 0) return b.start_time;
	}

	assert(false); // nu se poate ajunge aici
}

long long arrival_time(long long Y) {
	long long answer = arrival_time_brut(Y);
	return answer + 1LL * (stations.back() - stations[0]) * X_init;
}

#ifdef LOCAL
#undef int
// Grader
#include <cassert>
#include <cstdio>
#include <vector>

int main()
{
    int L, N, X, M, Q;
    assert(5 == scanf("%d %d %d %d %d", &L, &N, &X, &M, &Q));
    std::vector<long long> T(N);
    for (int i = 0; i < N; i++)
        assert(1 == scanf("%lld", &T[i]));
    std::vector<int> W(N);
    for (int i = 0; i < N; i++)
        assert(1 == scanf("%d", &W[i]));
    std::vector<int> S(M);
    for (int i = 0; i < M; i++)
        assert(1 == scanf("%d", &S[i]));
    std::vector<long long> Y(Q);
    for (int i = 0; i < Q; i++)
        assert(1 == scanf("%lld", &Y[i]));

    fclose(stdin);

    init(L, N, T, W, X, M, S);
    std::vector<long long> res(Q);
    for (int i = 0; i < Q; i++)
        res[i] = arrival_time(Y[i]);

    for (int i = 0; i < Q; i++)
        printf("%lld\n", res[i]);
    fclose(stdout);
    return 0;
}
#endif // LOCAL

Compilation message (stderr)

overtaking.cpp: In function 'long long int arrival_time_brut(long long int)':
overtaking.cpp:61: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]
   61 |  for(int i = 0; i + 1 < stations.size(); i++) {
      |                 ~~~~~~^~~~~~~~~~~~~~~~~

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