Submission #1255657

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255657		TadijaSebez	3개의 봉우리 (IOI25_triples)	C++20	78.80 / 100	1900 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> base={1, 2, 1, 4, 3, 2, 5, 1, 7, 2, 3, 4, 1, 2, 1, 3, 1, 2, 1, 4};
    vector<int> H(M,1);
    for(int i=0;i<M;i++)H[i]=base[i%base.size()];
    double start=(double)clock()/CLOCKS_PER_SEC;
    double duration=-1;
    ll now=count_triples(H);
    while(true){
        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;
        if(now>=K)return H;
        double now=(double)clock()/CLOCKS_PER_SEC;
        if(duration<0)duration=now-start;
        if(now-start+duration>1.9)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: 2.155 / 5
• Subtask 9: 0.7913 / 5
• Subtask 10: 0.3325 / 5
• Subtask 11: 0.3875 / 5
• Subtask 12: 0.1292 / 5