Submission #1253071

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253071		TadijaSebez	Triple Peaks (IOI25_triples)	C++20	34 / 100	2123 ms	1957192 KiB

triples

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

const int N=100005;

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,bitset<N>> Ls;
    map<int,bitset<N>> all;
    for(int i=0;i<n;i++){
        if(H[i]<N)Ls[H[i]-i].set(H[i]);
    }
    for(int i=n-1;i>=0;i--){
        bitset<N> Rs=all[H[i]+i]>>(N-H[i]);
        ans+=(Ls[H[i]-i]&Rs).count();
        if(H[i]%2==0 && Ls[H[i]-i].test(H[i]/2) && Rs.test(H[i]/2))ans--;
        if(N-H[i]>=0)all[H[i]+i].set(N-H[i]);
    }
    return ans;
}

mt19937 rng(time(0));
vector<int> Gen(int M){
    vector<int> ans;
    for(int i=0;i<M;i++){
        ans.pb(rng()%(M-1)+1);
    }
    return ans;
}

vector<int> construct_range(int M, int K) {
    vector<int> ans=Gen(M);
    vector<int> best;
    ll mx=0;
    printf("Solving %i %i\n",M,K);
    double start=(double)clock()/CLOCKS_PER_SEC;
    while(true){
        ll now=count_triples(ans);
        if(now>mx){
            mx=now;
            best=ans;
            printf("%lld\n",mx);
        }
        if(mx>=K)break;
        ans=Gen(M);
        double tme=(double)clock()/CLOCKS_PER_SEC-start;
        /*if(tme>60){
            printf("Failed %i %i\n",M,K);
            return best;
        }*/
    }
    printf("Solved %i %i\n",M,K);
    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 0 / 6
• Subtask 3: 10 / 10
• Subtask 4: 0 / 11
• Subtask 5: 16 / 16
• Subtask 6: 0 / 19
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5