Submission #1271834

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271834		win1702	Global Warming (CEOI18_glo)	C++20	15 / 100	2094 ms	14064 KiB

glo

// solve_calibration_n1000.cpp
// Brute-forced over segments [L,R] but with smart candidate-d generation.
// Correct for n <= 1000 in practice.
//
// Compile: g++ -O2 -std=c++17 solve_calibration_n1000.cpp -o solve
// Run: ./solve < input.txt

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int LIS_length(const vector<ll>& a) {
    vector<ll> tails;
    tails.reserve(a.size());
    for (ll x : a) {
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) tails.push_back(x);
        else *it = x;
    }
    return (int)tails.size();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    ll x;
    if (!(cin >> n >> x)) return 0;
    vector<ll> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    // baseline LIS without any calibration
    int best = LIS_length(a);

    // Pre-allocate container to reduce reallocs
    vector<ll> b(n);

    // We'll try every non-empty segment [L,R]
    for (int L = 0; L < n; ++L) {
        for (int R = L; R < n; ++R) {
            // Build candidate d's set (only values that can change relative order between
            // inside segment elements and outside elements).
            // For integers, the ordering a[i]+d < a[j] changes at d = a[j]-a[i]-k for small k.
            unordered_set<ll> cand;
            cand.reserve(512);
            // always try extremes (clamped)
            cand.insert(-x);
            cand.insert(x);
            cand.insert(0);

            for (int i = L; i <= R; ++i) {
                // compare with elements outside segment
                for (int j = 0; j < n; ++j) {
                    if (j >= L && j <= R) continue;
                    // critical values where relation between a[i]+d and a[j] changes:
                    // a[i]+d == a[j]  => d = a[j]-a[i]
                    // to handle strict inequality boundaries, also try +/-1 neighbors
                    ll base = a[j] - a[i];
                    // push base, base-1, base+1 (if in range)
                    if (base >= -x && base <= x) cand.insert(base);
                    if (base - 1 >= -x && base - 1 <= x) cand.insert(base - 1);
                    if (base + 1 >= -x && base + 1 <= x) cand.insert(base + 1);
                }
                // also try extremes relative to this element (clamped)
                if (-x - a[i] >= -x && -x - a[i] <= x) cand.insert(-x); // redundant but safe
                if ( x - a[i] >= -x &&  x - a[i] <= x) cand.insert(x);
            }

            // Now evaluate each candidate d
            // Note: cand size might be up to O(n)~1000 here; overall loops manageable for n<=1000.
            for (ll d : cand) {
                // d must be within [-x,x]
                if (d < -x || d > x) continue;
                // apply shift to segment
                for (int k = L; k <= R; ++k) b[k] = a[k] + d;
                // copy others unchanged
                for (int k = 0; k < L; ++k) b[k] = a[k];
                for (int k = R+1; k < n; ++k) b[k] = a[k];

                int lis = LIS_length(b);
                if (lis > best) best = lis;
            }
        }
    }

    cout << best << "\n";
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25