Submission #1250552

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250552		nikd	Triple Peaks (IOI25_triples)	C++20	26.90 / 100	2096 ms	1860 KiB

triples

#include "triples.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

long long count_triples(std::vector<int> H) {
  int n = H.size();
  ll sol = 0;
  for(int i = 0; i<n; i++){
    for(int j = i+1; j<n; j++){
        set<int> s;
        if(j-i == H[i]){
            if(j+H[j] < n && H[j+H[j]] == H[i]+H[j]){
                if(!s.count(j+H[j])){
                    sol++;
                    s.insert(j+H[j]);
                }
            }
            if(H[j] > H[i] && j + H[j] - H[i] < n && H[j+H[j]-H[i]] == H[j]-H[i]){
                if(!s.count(j+H[j] - H[i])){
                    sol++;
                    s.insert(j+ H[j]-H[i]);
                }
            }
        }
        if(j-i == H[j]){
            if(j+H[i] < n && H[j+H[i]] == H[j]+H[i]){
                if(!s.count(j+H[i])){
                    sol++;
                    s.insert(j+H[i]);
                }
            }
            if(H[i]-H[j] != H[j] && H[i] > H[j] && j + H[i] - H[j] < n && H[j+H[i]-H[j]] == H[i]-H[j]){
                if(!s.count(j+H[i]-H[j])){
                    sol++;
                    s.insert(j+H[i]-H[j]);
                }
            }
        }
        if(i + H[i] < n && i+H[i] > j && j-i == H[i+H[i]] && H[i] == H[j] + H[i+H[i]]){
            if(!s.count(i+H[i])){
                sol++;
                s.insert(i+H[i]);
            }
        }
        if(H[i] != H[j] && i+H[j] < n && i+H[j] > j && j-i == H[i+H[j]] && H[i+H[j]] + H[i] == H[j]){
            if(!s.count(i+H[j])){
                sol++;
                s.insert(i+H[j]);
            }
        }
    }
  }
  return sol;
}


std::vector<int> construct_range(int M, int K) {
    /*int NUM_BEST = 1;
    auto rec = [&](auto&& rec, vector<vector<int>> h, int n)->vector<int>{
        vector<vector<int>> hh((M-1)*h.size());
        for(int i = 0; i<h.size(); i++){
            for(int j = 1; j<M; j++){
                hh[i*(M-1)+j-1] = h[i];
                hh[i*(M-1)+j-1].push_back(j);
            }
        }
        vector<ll> str(hh.size());
        for(int i = 0; i<hh.size(); i++) str[i] = count_triples(hh[i]);
        vector<int> idx(hh.size());
        iota(idx.begin(), idx.end(), 0);
        sort(idx.begin(), idx.end(), [&](int a, int b){return str[a] > str[b];});
        vector<vector<int>> h_(NUM_BEST);
        for(int i =0; i<NUM_BEST; i++) h_[i] = hh[idx[i]];
        if(n == M) return h_[0];
        return rec(rec, h_, n+1);
    };
    vector<vector<int>> init(M-1);
    for(int i = 0; i<M-1; i++) init[i] = {i+1};
    vector<int> best = rec(rec, init, 2);
    cerr << count_triples(best) << '\n';
    return best;*/
    int kk = M/20;
    vector<int> sol(M);
    vector<int> tw = {13, 2, 1, 1, 3, 2, 3, 4, 1, 2, 1 ,3, 1, 6, 5, 4, 7, 6, 5, 1};
    for(int i = 0; i<M; i++) sol[i] = tw[i%20];
    return sol;
}

• 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: 5 / 5
• Subtask 8: 2.115 / 5
• Subtask 9: 0.8496 / 5
• Subtask 10: 0.3643 / 5
• Subtask 11: 0.425 / 5
• Subtask 12: 0.1417 / 5