Submission #1250947

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250947		fv3	Triple Peaks (IOI25_triples)	C++20	22.78 / 100	2096 ms	1864 KiB

triples

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

using namespace std;
using ll = long long;

#define all(x) x.begin(), x.end()

ll count_triples(vector<int> H) {
    const int N = H.size();
    ll res = 0;
 
    for (int i = 0; i < N; i++) {
        for (int j = i + 2; j < N; j++) {
            int mx_dist = j - i;
 
            if (H[i] > mx_dist || H[j] > mx_dist) continue;
 
            if (H[i] == mx_dist && H[j] == mx_dist) continue;
 
            if (H[i] == mx_dist) {
                if (H[i + H[j]] == H[i] - H[j]) res++;
                if (j - H[j] != i + H[j] && H[j - H[j]] == H[i] - H[j]) res++;
            } else if (H[j] == mx_dist) {
                if (H[i + H[i]] == H[j] - H[i]) res++;
                if (j - H[i] != i + H[i] && H[j - H[i]] == H[j] - H[i]) res++;
            } else if (H[i] + H[j] == mx_dist) {
                if (H[i + H[i]] == mx_dist) res++;
                if (H[i] != H[j] && H[i + H[j]] == mx_dist) res++;
            }
        }
    }
    return res;
}

vector<int> construct_range(int M, int K) {
    random_device rd;

    vector<int> best;
    ll best_score = 0;

    for (int i = 0; i < 200000 / M; i++) {
        mt19937 mt(rd());
        vector<int> H(M);
        for (int j = 0; j < M; j++) {
            H[j] = mt() % (3) + 1;
        }
        ll score = count_triples(H);
        if (score > best_score) {
            best_score = score;
            best = H;
        }
    }

    //cerr << best_score << "\n";
    
    return best;
}

//#include "grader.cpp"

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