Submission #1255647

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255647		TadijaSebez	Triple Peaks (IOI25_triples)	C++20	75 / 100	2095 ms	24692 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> H(M,1);
    vector<int> ord(M);
    iota(ord.begin(),ord.end(),0);
    for(int t=1;t<=10;t++){
        shuffle(ord.begin(),ord.end(),rng);
        for(int i:ord){
            int best=H[i];
            ll now=count_triples(H);
            for(int j=1;j<=M;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;
            if(now>=K)return H;
        }
    }
    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: 0 / 5
• Subtask 9: 0 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5