Submission #1265782

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265782		coderg	Triple Peaks (IOI25_triples)	C++20	100 / 100	1108 ms	24692 KiB

triples

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define el '\n'

const int maxn=2e5+5;
unordered_map<int,vector<int>> m;
int n;
ll count_triples(vector<int> h){
    n=h.size();
    ll cnt=0;
    for(ll j=0;j<n;j++){
        int l=j-h[j];
        if(l>=0){
            int x=h[l],y=h[j]-x;
            if(y>0){
                if(h[l+x]==y)cnt++;
                if(y!=x && h[l+y]==y)cnt++;
            }
        }
        int r=j+h[j];
        if(r<n){
            int x=h[r],y=h[j]-x;
            if(y>0){
                if(h[j+x]==y)cnt++;
                if(y!=x && h[j+y]==y)cnt++;

            }
        }
    }
    for(ll k=0;k<n;k++){
        int hk=h[k];
        for(auto i:m[k-hk]){
            int j1=i+h[i],j2=i+h[k];
            if(j1<k && h[j1]==k-i)cnt++;
            if(j2<k && j2!=j1 && h[j2]==k-i)cnt++;
        }
        m[k+h[k]].push_back(k);
    }
    return cnt;
}

std::vector<int> construct_range(int m,int k){
    vector<int> ans1={
        4,3,1,2,1,
        4,3,2,7,6,
        5,8,11,10,9,
        1,7,2,3,4,
    };
    if(m<=20){
        while(ans1.size()>m || ans1.back()>=m)ans1.pop_back();
        return ans1;
    }
    int n=m;
    vector<int> x={-1},y={1},used(2*n),chosen={0},h(n),score(2*n,-1e9);
    for(int i=2;i<2*n;i+=2)score[i]=1;

    while(true){
        auto it=max_element(score.begin(),score.end());
        int mx=*it,best_score=it-score.begin();
        if(mx==0)break;
        for(auto xi:chosen){
            int sum=xi+best_score;
            if(sum<n*2 && !used[sum]){
                used[sum]=1;
                x.push_back(min(xi,best_score));
                y.push_back(max(xi,best_score));
                for(auto yi:chosen){
                    int z=sum-yi;
                    if(0<=z && z<2*n)score[z]--;
                }
            }
        }
    
        for(int i=0;best_score+i<2*n;i+=2)if(!used[best_score+i])score[i]++;
        chosen.push_back(best_score);
        score[best_score]=-1e9;
    }
        for(ll i=0;i<n;i++)h[(x[i]+y[i])/2]=(y[i]-x[i])/2;

        ll cnt=count_triples(h);
        while(cnt<k){
            for(ll i=0;i<k;i++){
                for(ll j=1;j<=n-1;j++){
                    int temp=h[i];
                    h[i]=j;
                    ll cnt2=count_triples(h);
                    if(cnt2>cnt)cnt=cnt2;
                    else h[i]=temp;
                }
            }
        }
    
    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