Submission #1255845

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255845		TadijaSebez	Triple Peaks (IOI25_triples)	C++20	100 / 100	1435 ms	20788 KiB

triples

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

const int S=350;

ll EasyPart(vector<int> H){
    int n=H.size();
    ll ans=0;
    for(int mid=1;mid<n-1;mid++){
        int L=mid-H[mid];
        if(L>=0){
            if(H[L]>H[mid]){
                int R=L+H[L];
                if(R<n && H[R]==R-mid){
                    ans++;
                }
            }
            int R=mid+H[L];
            if(R<n && H[R]==R-L){
                ans++;
            }
        }
        int R=mid+H[mid];
        if(R<n){
            if(H[R]>H[mid]){
                int L=R-H[R];
                if(L>=0 && H[L]==mid-L){
                    ans++;
                }
            }
            int L=mid-H[R];
            if(L>=0 && H[L]==R-L){
                ans++;
            }
        }
        L=mid-H[mid];
        R=mid+H[mid];
        if(L>=0 && R<n && max(H[L],H[R])==2*H[mid] && min(H[L],H[R])==H[mid]){
            ans--;
        }
    }
    return ans;
}

ll count_triples(vector<int> H) {
    int n=H.size();
    ll ans=EasyPart(H);
    {
        vector<vector<int>> Ls(n),Rs(n);
        for(int i=0;i<n;i++){
            if(i+H[i]<n)Ls[i+H[i]].pb(H[i]);
            if(i-H[i]>=0)Rs[i-H[i]].pb(H[i]);
        }
        for(int mid=0;mid<n;mid++){
            sort(Ls[mid].begin(),Ls[mid].end());
            sort(Rs[mid].begin(),Rs[mid].end());
            int j=(int)Rs[mid].size()-1;
            for(int x:Ls[mid]){
                while(j>=0 && x+Rs[mid][j]>H[mid]){
                    j--;
                }
                if(j>=0 && x+Rs[mid][j]==H[mid]){
                    ans++;
                }
            }
        }
    }
    map<int,vector<int>> Ls;
    for(int i=0;i<n;i++){
        Ls[H[i]-i].pb(i);
    }
    vector<int> large;
    for(auto& it:Ls){
        if(it.second.size()>=S)large.pb(it.first);
        else{
            for(int a=0;a<it.second.size();a++){
                for(int b=a+1;b<it.second.size();b++){
                    int i=it.second[a];
                    int j=it.second[b];
                    int k=i+H[j];
                    if(k<n && H[i]==k-j && H[k]==j-i && H[i]!=H[k]){
                        ans++;
                    }
                }
            }
        }
    }
    for(int k=0;k<n;k++){
        for(int x:large){
            int j2=H[k]+k-x;
            if(j2%2==0){
                int j=j2/2;
                int i=j-H[k];
                if(j<k && i>=0 && H[j]==k-i && H[i]==k-j && H[i]!=H[k]){
                    ans++;
                }
            }
        }
    }
    return ans;
}

mt19937 rng(time(0));

vector<int> construct_range(int M, int K) {
    vector<int> S={0};
    vector<bool> used(2*M,false);
    vector<bool> done(2*M,false);
    vector<int> cnt(2*M,1);
    used[0]=true;
    int was=0;
    while(true){
        vector<int> best={};
        int mx=was;
        for(int i=2;i<2*M;i+=2){
            if(!used[i]){
                int now=was+cnt[i];
                if(mx<now){
                    mx=now;
                    best={i};
                }else if(mx==now){
                    best.pb(i);
                }
            }
        }
        if(mx==was)break;
        int idx=best[rng()%best.size()];
        for(int x:S){
            int z=x+idx;
            if(z<2*M && !done[z]){
                done[z]=true;

                for(int y:S){
                    int z=x+idx-y;
                    if(0<z&&z<2*M)cnt[z]--;
                }
            }
        }
        for(int i=0;i<2*M;i+=2){
            int z=i+idx;
            if(0<z&&z<2*M && !done[z]){
                cnt[i]++;
            }
        }
        S.pb(idx);
        used[idx]=true;
        was=mx;
    }
    vector<int> H(M);
    H[0]=1;
    for(int i=(int)S.size()-1;i>=0;i--){
        for(int j=0;j<i;j++){
            int X=S[i];
            int Y=S[j];
            if(X>Y)swap(X,Y);
            if(X+Y<2*M){
                H[(X+Y)/2]=(Y-X)/2;
            }
        }
    }

    double start=(double)clock()/CLOCKS_PER_SEC;
    double duration=-1;
    ll now=count_triples(H);
    while(now<K){
        int i=rng()%M;
        int best=H[i];
        for(int j=max(1,best-3);j<=min(M,best+3);j++){
            if(j!=best){
                H[i]=j;
                ll tmp=count_triples(H);
                if(tmp>now || (tmp==now && rng()%2==0)){
                    now=tmp;
                    best=j;
                }
            }
        }
        H[i]=best;
        double now=(double)clock()/CLOCKS_PER_SEC;
        if(duration<0)duration=now-start;
        if(now-start+duration>1.8)break;
    }
    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