Submission #1252224

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252224		dreamnguyen	Triple Peaks (IOI25_triples)	C++20	100 / 100	1037 ms	24688 KiB

triples

#include <bits/stdc++.h>
#define el '\n'
typedef long long llo;
#define fn(i,a,b) for (int i = a; i <= b; i++)
#define rn(i,a,b) for (int i = a; i >= b; i--)
using namespace std;

const int nmax = 2e5 + 5;
unordered_map <int, vector <int>> m;
int n;
llo count_triples(vector <int> H)
{
    n = H.size();
    llo cnt = 0;
    for (int j=0; j<n; j++)
    {
        int l = j - H[j];
        if(l >= 0)
        {
            int x = H[l];
            int y = H[j] - x;
            if(y > 0)
            {
                if(H[l + x] == y) cnt++;
                if(y != x && H[l + y] == y) cnt++;
            }
        }
        int r = j + H[j];
        if(r < n)
        {
            int x = H[r];
            int y = H[j] - x;
            if(y > 0)
            {
                if(H[j + x] == y) cnt++;
                if(y != x && H[j + y] == y) cnt++;
            }
        }
    }
    for (int k = 0; k < n; ++k)
    {
        int hk = H[k];
        for (int i : m[k - hk])
        {
            int j1 = i+H[i];
            int j2 = i+H[k];
            if (j1<k && H[j1]==k-i) cnt++;
            if (j2<k && j2!=j1 && H[j2]==k-i) cnt++;
        }

        m[k + H[k]].push_back(k);
    }
    return cnt;
}

std::vector<int> construct_range(int M, int K){
    vector<int> ans1 = {
        4,  3,  1,  2,  1,
        4,  3,  2,  7,  6,
        5,  8, 11, 10,  9,
        1,  7,  2,  3,  4,
    };

    if(M <= 20){
        while(ans1.size() > M || ans1.back() >= M) ans1.pop_back();
        return ans1;
    }
    int N = M;
    vector<int> X = {-1}, Y = {1}, used(N*2), chosen = {0}, H(N), score(N*2, -1e9);
    for (int i=2 ; i < N*2; i+=2) score[i] = 1;

    while(true){
        auto it = max_element(score.begin(), score.end());
        int mx = *it, best_score = it - score.begin();

        if (mx == 0) break;

        for (int x : chosen){
            int sum = x + best_score;
            if (sum < N*2 && !used[sum]){
                used[sum] = 1;

                X.push_back(min(x, best_score));
                Y.push_back(max(x, best_score));

                for (int y : chosen){
                    int z = sum - y;
                    if (0 <= z && z < N*2) score[z]--;
                }
            }
        }

        for (int i = 0; best_score + i < N*2; i+=2) if(!used[best_score + i]) score[i]++;

        chosen.push_back(best_score);
        score[best_score] = -1e9;
    }
    for (int i = 0; i<N; i++) H[(X[i] + Y[i]) / 2] = (Y[i] - X[i]) / 2;
    
    llo cnt = count_triples(H);
    while(cnt < K){
        for (int i = 0; i < N; i++){
            for (int j = 1; j <= N-1; j++){
                int tmp = H[i];
                H[i] = j;
                
                llo cnt2 = count_triples(H);
                if (cnt2 > cnt) cnt = cnt2;
                else H[i] = tmp;
            }
        }
    }

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