Submission #1274324

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274324		biank	Triple Peaks (IOI25_triples)	C++20	100 / 100	440 ms	31136 KiB

triples

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

using namespace std;

#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)

using vi = vector<int>;
using ll = long long;

#define fst first
#define snd second

#define sz(x) int(x.size())
#define all(x) begin(x), end(x)

#define pb push_back
#define eb emplace_back

ll count_triples(vi h) {
    const int n = sz(h);
    const int sq = sqrt(n);
    vector<tuple<int, int, int>> triples;
    int ret = 0;
    forn(i, n) {
        int j = i + h[i];
        if (j >= n) continue;
        {
            int k = j + h[j];
            if (k < n && h[k] == k - i && h[i] != h[j]) ret++;
        }
        {
            int k = j + h[j] - h[i];
            if (j < k && k < n && h[k] == k - j && h[i] != h[k]) ret++;
        }
    }
    forn(j, n) {
        int i = j - h[j];
        if (i < 0) continue;
        {
            int k = j + h[i];
            if (k < n && h[k] == k - i) ret++;
        }
        {
            int k = j + h[i] - h[j];
            if (j < k && k < n && h[k] == k - j && h[j] != h[k]) ret++;
        }
    }
    forn(j, n) {
        int k = j + h[j];
        if (k >= n) continue;
        int i = j - h[k];
        if (i >= 0 && h[i] == k - i) ret++;
    }
    vector<vi> diag1(2 * n), diag2(2 * n);
    forn(i, n) {
        diag1[h[i] - i + n].pb(i);
        diag2[h[i] + i].pb(i);
    }
    for (auto d : diag1) {
        if (sz(d) < sq) {
            forn(idx1, sz(d)) forsn(idx2, idx1 + 1, sz(d)) {
                int i = d[idx1], j = d[idx2];
                int k = j + h[i];
                if (k < n && h[j] == k - i && h[k] == j - i) ret++;
            }
        } else {
            for (int j : d) for (int k : diag2[h[j] + j]) {
                if (j >= k) continue;
                int i = j - h[k];
                if (i >= 0 && h[i] == k - j && h[j] == k - i) ret++;
            }
        }
    }
    return ret;
}

const int INF = 1e9;

vi construct_range(int M, int K) {
    vi ret = {};
    int best = 0;
    int seed = -1247761304;
    while (best < K) {
        mt19937 rng(seed++);
        int S = sqrt(6 * M);
        S = uniform_int_distribution<int>(S * 2 / 3, S * 4 / 3 + 1)(rng);
        set<int> s;
        vi diag(S);
        forn(i, S) {
            diag[i] = uniform_int_distribution<int>(-M / 2, M * 3 / 2 + 1)(rng);
            diag[i] /= 2, diag[i] *= 2;
            if (s.count(diag[i])) i--;
            else s.insert(diag[i]);
        }
        vi ans(M, INF);
        forn(i, S) forsn(j, i + 1, S) {
            int idx = (diag[i] + diag[j]) / 2;
            int val = abs(diag[i] - diag[j]) / 2;
            if (0 <= idx && idx < M && 1 <= val && val < M) ans[idx] = min(ans[idx], val);
        }
        forn(i, M) if (ans[i] == INF) {
            ans[i] = uniform_int_distribution<int>(1, 2)(rng);
        }
        int triples = count_triples(ans);
        if (triples > best) best = triples, ret = ans;
    }
    return ret;
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 6 / 6
• Subtask 3: 10 / 10
• Subtask 4: 11 / 11
• Subtask 5: 16 / 16
• Subtask 6: 19 / 19
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 5 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 5 / 5