Submission #1215523

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215523		trimkus	Overtaking (IOI23_overtaking)	C++20	9 / 100	4 ms	4424 KiB

overtaking

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

using namespace std;
using ll = long long;

int N, L;
vector<int> W, S;
int X, M;
vector<ll> T;
ll expected[1001][1001];
vector<int> tot_ord[1001];
int pos[1001][1001];

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;
    M = _M;
    N = _N;
    T = _T;
    W = _W;
    X = _X;
    S = _S;
    // W.push_back(X);
    // vector<vector<ll>> exp(N, vector<ll>(M));
    vector<int> ord(N);
    iota(begin(ord), end(ord), 0);
    for (int i = 0; i < N; ++i) {
        expected[i][0] = T[i];
    }
    for (int j = 1; j < M; ++j) {
        sort(begin(ord), end(ord), [&](int x, int y){
            if (expected[x][j - 1] != expected[y][j - 1]) return expected[x][j - 1] < expected[y][j - 1];
            return W[x] < W[y];
        });
        tot_ord[j - 1] = ord;
        ll tim = -1;
        for (int it = 0; it < N; ++it) {
            int i = ord[it];
            pos[j - 1][i] = it;
            // cerr << W[i] << " ";
            expected[i][j] = expected[i][j - 1] + 1LL * W[i] * (S[j] - S[j - 1]);
            expected[i][j] = max(tim, expected[i][j]);
            tim = max(expected[i][j], tim);
        }
        // cerr << endl;
        if (j == M - 1) {
            sort(begin(ord), end(ord), [&](int x, int y){
                if (expected[x][j - 1] != expected[y][j - 1]) return expected[x][j - 1] < expected[y][j - 1];
                return W[x] < W[y];
            });
            for (int it = 0; it < N; ++it) {
                int i = ord[it];
                pos[j][i] = it;
            }
        }
    }
}

bool lessi(ll e, int x, int j) {
    if (e != expected[x][j]) return e <= expected[x][j];
    return X <= W[x];
}

bool strict_less(ll e, int x, int j) {
    if (e != expected[x][j]) return e < expected[x][j];
    return X < W[x]; 
}

int search(ll e, int j) {
    int l = 0, r = N - 1;
    while (l < r) {
        int mid = (l + r) / 2;
        if (lessi(e, mid, j)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return r;
}

long long arrival_time(long long Y)
{
    int id = search(Y, 0);
    ll e = Y;
    // cerr << Y << ":\n";
    for (int i = 1; i < M; ++i) {
        id = search(e, i - 1);
        if (strict_less(e, id, i - 1)) id -= 1;
        e = e + 1LL * X * (S[i] - S[i - 1]);
        if (id >= 0) {
            // cerr << id << " " << e << " " << expected[id][i] << " ?= " << strict_less(e, id, i) << endl;
            e = max(e, expected[id][i]);
        }
    }
    // cerr << Y << ":\n";
    // for (int j = 0; j < M; ++j) {
    //     for (int i = 0; i <= N; ++i) {
    //         cerr << exp[i][j] << " ";
    //     }
    //     cerr << "\n";
    // }
    // cerr << "\n";
    return e;
}

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