Submission #20622

#	Time	Username	Problem	Language	Result	Execution time	Memory
20622		model_code	Shortcut (IOI16_shortcut)	C++11	71 / 100	2000 ms	3196 KiB

shortcut

// name = shortcut_iz_n2log.cpp, type = cpp.g++11

#include "shortcut.h"
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
//#include "shortcut.h"

using namespace std;

typedef long long ll;

const ll INF = (ll)1e18;
long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c) {
    vector<ll> x(n);
    x[0] = 0;
    for (int i = 1; i < n; i++) x[i] = x[i - 1] + l[i - 1];

    ll L = 0, R = INF;
    while (R - L > 1) {
        ll M = ((ll)L + R) / 2;

        ll minSum = -INF, maxSum = INF;
        ll minDif = -INF, maxDif = INF;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // abs(x[i] - l) + abs(x[j] - r) <= M - c - d[i] - d[j]
                // abs(x[i] - l) <= M - c - d[i] - d[j] - abs(x[j] - r)
                // x[i] - l <= M - c - d[i] - d[j] - abs(x[j] - r)
                // x[i] - l >= -M + c + d[i] + d[j] + abs(x[j] - r)

                // abs(x[j] - r) <= M - c - d[i] - d[j] - x[i] + l
                // x[j] - r <= M - c - d[i] - d[j] - x[i] + l
                // l + r >= -M + c + d[i] + d[j] + x[i] + x[j]
                // x[j] - r >= -M + c + d[i] + d[j] + x[i] - l
                // l - r >= -M + c + d[i] + d[j] + x[i] - x[j]  


                // abs(x[j] - r) <= M - c - d[i] - d[j] + x[i] - l
                // x[j] - r <= M - c - d[i] - d[j] + x[i] - l
                // l - r <= M - c - d[i] - d[j] + x[i] - x[j]
                // x[j] - r >= -M + c + d[i] + d[j] - x[i] + l
                // l + r <= M - c - d[i] - d[j] + x[i] + x[j]

                if (x[j] - x[i] + d[i] + d[j] > M) {
                    minSum = max(minSum, -M + c + d[i] + d[j] + x[i] + x[j]);
                    maxSum = min(maxSum, M - c - d[i] - d[j] + x[i] + x[j]);
                    minDif = max(minDif, -M + c + d[i] + d[j] + x[i] - x[j]);
                    maxDif = min(maxDif, M - c - d[i] - d[j] + x[i] - x[j]);
                }
            }
        }
        bool found = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                ll sum = x[i] + x[j];
                ll dif = x[i] - x[j];
                if (minSum <= sum && sum <= maxSum && minDif <= dif && dif <= maxDif) {
                    found = 1;
                }
            }
        }
        if (found) R = M;
        else L = M;
    }
    return R;
}

• 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