Submission #1273015

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273015		duckindog	Shortcut (IOI16_shortcut)	C++20	71 / 100	2096 ms	1340 KiB

shortcut

#include <bits/stdc++.h>

#include "shortcut.h"

using namespace std;

const long long MAX = 1'000'000'000'000'000'000;

const int N = 3'000 + 10;

struct Rec { 
    long long x, y, u, v;
    Rec(long long x = -MAX, long long y = -MAX, long long u = MAX, long long v = MAX) : x(x), y(y), u(u), v(v) {}
};  
Rec merge(const Rec& a, const Rec& b) { 
    return Rec(max(a.x, b.x), max(a.y, b.y), min(a.u, b.u), min(a.v, b.v));
}

long long find_shortcut(int n, vector<int> l, vector<int> d, int c) {
    vector<long long> p(n); 
    for (int i = 1; i < n; ++i) p[i] = p[i - 1] + l[i - 1];

    auto chk = [&](long long mid) { 
        auto calRec = [&](int i, int j, long long c) { 
            return Rec(p[i] + p[j] + d[i] + d[j] - c, 
                        p[i] - p[j] + d[i] + d[j] - c, 
                        p[i] + p[j] - d[i] - d[j] + c,
                        p[i] - p[j] - d[i] - d[j] + c);
        };

        Rec rec;
        for (int i = 0; i < n; ++i) { 
            for (int j = i + 1; j < n; ++j) { 
                if (p[j] - p[i] + d[i] + d[j] <= mid) continue;
                rec = merge(rec, calRec(i, j, mid - c));
            }
        }
        if (rec.x > rec.u || rec.y > rec.v) return false;
        
        for (int i = 0; i < n; ++i) { 
            long long L = max(rec.x - p[i], rec.y + p[i]),
                        R = min(rec.u - p[i], rec.v + p[i]);
            auto it = lower_bound(p.begin(), p.end(), L);
            if (it != p.end() && *it <= R) return true;
        }
        return false;
    };

    long long le = 0, ri = MAX, ret = MAX;
    while (le <= ri) { 
        auto mid = (le + ri) >> 1;
        if (chk(mid)) ri = mid - 1, ret = mid;
        else le = mid + 1;
    }
    return ret;
}

Compilation message (stderr)

shortcut.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
shortcut_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• Subtask 1: 9 / 9
• Subtask 2: 14 / 14
• Subtask 3: 8 / 8
• Subtask 4: 7 / 7
• Subtask 5: 33 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3