Submission #1263727

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263727		gotkako	Triple Peaks (IOI25_triples)	C++20	78.11 / 100	520 ms	88248 KiB

triples

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

random_device rnd;
mt19937 mt(rnd());
double mtd(){return (0.0+mt())/numeric_limits<unsigned int>::max();}

bool test = true;
long long count_triples(std::vector<int> H) {
    int N = H.size();
    long long answer = 0;
    if(N <= 200000){
        long long n1 = N,n2 = n1*n1;
        unordered_set<long long> S;
        for(int i=0; i<N; i++){
            long long k = i-H.at(i);
            if(k >= 0){
                vector<long long> L = {i+H.at(k),i-H.at(k),k+H.at(k),k-H.at(k)};
                sort(L.begin(),L.end());
                L.erase(unique(L.begin(),L.end()),L.end());
                for(auto l : L){
                    if(l < 0 || l >= N) continue;
                    if(l == i || l == k) continue;
                    
                    int a = i,b = k,c = l;
                    if(a > b) swap(a,b);
                    if(b > c) swap(b,c);
                    if(a > b) swap(a,b);

                    int h1 = H.at(i),h2 = H.at(k),h3 = H.at(l);
                    if(max({h1,h2,h3}) == h2 && (b-a == h3 || c-b == h1)) continue;
                    if(S.count(a*n2+b*n1+c)) continue;
                    S.insert(a*n2+b*n1+c);

                    if(h1 > h2) swap(h1,h2);
                    if(h2 > h3) swap(h2,h3);
                    if(h1 > h2) swap(h1,h2);
                    
                    answer += (h3 == c-a && ((h1 == b-a && h2 == c-b) || (h1 == c-b && h2 == b-a)));
                }
            }
            k = i+H.at(i);
            if(k < N){
                vector<long long> L = {i+H.at(k),i-H.at(k),k+H.at(k),k-H.at(k)};
                sort(L.begin(),L.end());
                L.erase(unique(L.begin(),L.end()),L.end());
                for(auto l : L){
                    if(l < 0 || l >= N) continue;
                    if(l == i || l == k) continue;
                    
                    int a = i,b = k,c = l;
                    if(a > b) swap(a,b);
                    if(b > c) swap(b,c);
                    if(a > b) swap(a,b);
                    
                    int h1 = H.at(i),h2 = H.at(k),h3 = H.at(l);
                    if(max({h1,h2,h3}) == h2 && (b-a == h3 || c-b == h1)) continue;
                    if(S.count(a*n2+b*n1+c)) continue;
                    S.insert(a*n2+b*n1+c);

                    if(h1 > h2) swap(h1,h2);
                    if(h2 > h3) swap(h2,h3);
                    if(h1 > h2) swap(h1,h2);
                    answer += (h3 == c-a && ((h1 == b-a && h2 == c-b) || (h1 == c-b && h2 == b-a)));
                }
            }
        }
        vector<pair<int,int>> G(N);
        vector<int> L(N),R(N);
        for(int i=0; i<N; i++) G.at(i) = {H.at(i)-i+N,H.at(i)-(N-1-i)+N};
        int zero = 0;
        for(int i=0; i<N; i++){
            int h = H.at(i);
            L.at(i) = h+zero;
            zero--;
        }
        zero = 0;
        for(int i=N; i--;){
            int h = H.at(i);
            R.at(i) = h+zero;
            zero--;
        }

        vector<vector<int>> Cr(N+N),Cl(N+N);
        for(int i=N-1; i>=0; i--){
            int r = R.at(i)+N;
            Cr.at(r).push_back(i);
        }

        for(int i=0; i<N; i++){
            int l = L.at(i)+N,r = R.at(i)+N;
            Cr.at(r).pop_back();

            auto [nowl,nowr] = G.at(i);
            if(Cl.at(nowl).size() <= Cr.at(nowr).size()){
                for(auto posl : Cl.at(nowl)){
                    int posr = posl+H.at(i);
                    if(posr >= N) break;
                    if(posl < i && i < posr){
                        int h1 = H.at(posl),h2 = H.at(i),h3 = H.at(posr);
                        answer += (posr-i == h1 && i-posl == h3);
                    }
                }
            }
            else{
                for(auto posr : Cr.at(nowr)){
                    int posl = posr-H.at(i);
                    if(posl < 0) continue;
                    if(posl < i && i < posr){
                        int h1 = H.at(posl),h2 = H.at(i),h3 = H.at(posr);
                        answer += (posr-i == h1 && i-posl == h3);
                    }
                }
            }

            Cl.at(l).push_back(i);
        }
    }
    return answer;
}


double timelimit = 55*CLOCKS_PER_SEC;

std::vector<int> construct_range(int M, int K) {
    double starttime = clock();
    vector<int> ret;
    while(ret.size() < M){
        for(auto v : {1,2,1,4,3,2,3,1,1,2}) ret.push_back(v);
    }
    return ret;
    auto bestret = ret;
    long long now = count_triples(ret);
    long long best = now;
    double starttemp = 2,endtemp = 0.2;
    while(now < K){
        double time = clock()-starttime;
        if(time > timelimit) break;
        int kind = mt()%3;

        if(kind == 0){
            int pos = mt()%M,v = mt()%(M/2)+1;
            int memo = ret.at(pos);
            ret.at(pos) = v;
            long long next = count_triples(ret);
            double temp = starttemp+(endtemp-starttemp)/timelimit;
            double prob = exp((next-now)/temp);
            if(mtd() < prob){
                now = next;
                if(now > best) now = best,bestret = ret;
            }
            else ret.at(pos) = memo;
        }
        else if(kind == 1){
            int pos = mt()%M,pos2 = pos;
            while(pos == pos2) pos2 = mt()%M;
            swap(ret.at(pos),ret.at(pos2));
            long long next = count_triples(ret);
            double temp = starttemp+(endtemp-starttemp)/timelimit;
            double prob = exp((next-now)/temp);
            if(mtd() < prob){
                now = next;
                if(now > best) now = best,bestret = ret;
            }
            else swap(ret.at(pos),ret.at(pos2));
        }
        else{
            int pos = mt()%M,pos2 = pos,pos3 = pos;
            while(pos == pos2) pos2 = mt()%M;
            while(pos == pos3 || pos2 == pos3) pos3 = mt()%M;
            
            swap(ret.at(pos),ret.at(pos2)),swap(ret.at(pos2),ret.at(pos3));
            long long next = count_triples(ret);
            double temp = starttemp+(endtemp-starttemp)/timelimit;
            double prob = exp((next-now)/temp);
            if(mtd() < prob){
                now = next;
                if(now > best) now = best,bestret = ret;
            }
            else swap(ret.at(pos2),ret.at(pos3)),swap(ret.at(pos),ret.at(pos2));
        }
    }

    return bestret;
}

• 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: 4.6667 / 5
• Subtask 8: 1.87 / 5
• Subtask 9: 0.7498 / 5
• Subtask 10: 0.3214 / 5
• Subtask 11: 0.375 / 5
• Subtask 12: 0.125 / 5