Submission #1251837

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251837		liamislazy	Triple Peaks (IOI25_triples)	C++20	40 / 100	2096 ms	4684 KiB

triples

#include "triples.h"
#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;

long long count_triples(vector <signed> H)
{
    int n = H.size();
    long long ans = 0;
    //Hj = j - i
    for(int j = 0; j < n; j++)
    {
        for(int i = max(0, j - H[j] + 1); i < j && i + H[j] < n; i++)
        {
            int k = i + H[j];
            int x = H[k], y = H[i];
            int d1 = j - i, d2 = k - j;
            if((H[k] == d1 && H[i] == d2) || (H[k] == d2 && H[i] == d1)) ans++;
        }
        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) ans++;
                if(y != x && H[l + y] == y) ans++;
            }
        }
        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) ans++;
                if(y != x && H[j + y] == y) ans++;
            }
        }
    }
    return ans;
}

std::vector<int> construct_range(int M, int K){
    int n = M;
    vector<int> chosen = {0}, score(2*n, -1e9), X, Y, H(n);
    vector<bool> used(2*n, 0);
    for(int i = 2; i < 2*n; i += 2){
        score[i] = 1;
    }
    while(true){
        int best_score = -1e9, best_pos = -1;
        fn(i,0,2*n-1){
            if(score[i] > best_score){
                best_score = score[i];
                best_pos = i;
            }
        }
        if (best_score <= 0) break;

        for(int x : chosen){
            int sum = x + best_pos;
            if(sum >= 2*n || used[sum]) continue;
            used[sum] = 1;

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

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

        for(int i = best_pos; best_pos + i < 2*n; i += 2){
            if (!used[best_pos + i]) score[i]++;
        }

        chosen.push_back(best_pos);
        score[best_pos] = -1e9;
    }

    for (int i = 0; i < (int)X.size(); ++i) {
        int mid = (X[i] + Y[i]) >> 1;
        int diff = (Y[i] - X[i]) >> 1;
        if (mid >= 0 && mid < n) {
            H[mid] = diff;
        }
    }


    llo cnt = count_triples(H);
    while (cnt < K) {
        for (int i = 0; i < n; ++i) {
            int best_val = H[i];
            for (int j = 1; j < n; ++j) {
                H[i] = j;
                llo new_cnt = count_triples(H);
                if (new_cnt > cnt) {
                    cnt = new_cnt;
                    best_val = j;
                }
            }
            H[i] = best_val;
        }
    }
    return H;
}

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