Submission #1249450

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249450		jtnydv25	Triple Peaks (IOI25_triples)	C++20	95 / 100	2095 ms	31300 KiB

triples

#include "triples.h"

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

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

#ifdef LOCAL
#include <print.h>
#else
#define trace(...)
#define endl "\n" // remove in interactive
#endif

// mt19937_64 for 64 bit
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int getRand(int x, int y){
	return uniform_int_distribution<int>(x, y)(rng);
}


long long count_triples(vector<int> H){
    int n = H.size();
    const int OFFSET = n;
    vector<vector<int>> at_sum(2 * n + 1), at_diff(2 * n + 1);
    for(int i = 0; i < n; i++){
        at_sum[i + H[i]].push_back(i);
        at_diff[i - H[i] + OFFSET].push_back(i);
    }
    int ans = 0;
    // right-most is highest
    for(int k = 0; k < n; k++){
        int i = k - H[k];
        if(i < 0 || H[i] >= H[k]) continue;
        {
            int j = k  - H[i];
            if(H[j] == j - i) ans++;
        }

        {
            int j = i + H[i];
            if(H[j] == k - j && k + i != 2 * j) ans++;
        }
    }
    // left-most is highest
    for(int i = 0; i < n; i++){
        int k = i + H[i];
        if(k >= n || H[k] >= H[i]) continue;
        {
            int j = k - H[k];
            if(H[j] == j - i) ans++;
        }

        {
            int j = i + H[k];
            if(H[j] == k - j && k + i != 2 * j) ans++;
        }
    }
    // middle is highest
    for(int j = 0; j < n; j++){
        for(int i: at_sum[j]){
            if(H[i] >= H[j] || i >= j) continue;
            int Hk = H[j] - H[i];
            int k = j + Hk;
            if(k < n && H[k] == Hk && H[i] != Hk) {
                ans++;
            }
        }

        if(sz(at_sum[j + H[j]]) < sz(at_diff[j - H[j] + OFFSET])){
            for(int k: at_sum[j + H[j]]){
                if(H[k] >= H[j] || k <= j) continue;
                int i = j - H[k];
                if(i < 0) continue;
                if(H[i] + H[k] == H[j]) ans++;
            }
        } else{
            for(int i: at_diff[j - H[j] + OFFSET]){
                if(H[i] >= H[j] || i >= j) continue;
                int k = j + H[i];
                if(k >= n) continue;
                if(H[k] + H[i] == H[j]) ans++;
            }
        }
    }
    return ans;
}

std::vector<int> construct_range(int n, int req) {
    int mx = 0;
    while(true){ // keep running
        for(int t = (n==20 ? 1 : sqrt(n)); t * t <= 10 * n; t = max(t + 1,(int)(t * 1.11))){
            vector<int> H(n, -1);
            vector<bool> used(n + 1, false);
            for(int qq = 0; qq < 5; qq++){
                set<int> vals;
                // return 0;
                for(int i = 2; i <= t; i+=2) vals.insert(i);
                while(sz(vals) < 2 * t){
                    int upper = n == 20 ? n/2: 2 * n / 3;
                    vals.insert(getRand(1, upper) * 2);
                }
                vector<int> V(all(vals));
                for(int diff: V){
                    for(int sum: V){
                        if((sum + diff) % 2 == 1) continue;
                        int i = (sum + diff) / 2;
                        int h = (sum - diff) / 2;
                        if(h >= n || h < 1) continue;
                        if(i < 0 || i >= n) continue;
                        if(used[i]) continue;
                        if(h > 0 && h < n){
                            H[i] = h;
                            // used[i] = true;
                        }
                    }
                }
                for(int i = 0; i < n; i++){
                    if(H[i] != -1){
                        used[i] = true;
                    }
                }
            }
            int filled = n;
            for(int i = 0; i < n; i++){
                if(H[i] == -1){
                    H[i] = getRand(1, 2);
                    filled--;
                }
            }
            if(n == 20){
                H = {2, 1, 1, 3, 2, 3, 4, 1, 2, 1, 3, 1, 3, 2, 3, 4, 1, 2, 1, 3};
            }
            int got = count_triples(H);
            if(got >= req){
                return H;
            }
        }
    }
}

• 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: 0 / 5
• Subtask 9: 5 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 5 / 5