Submission #1254249

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254249		KLPP	Triple Peaks (IOI25_triples)	C++20	76.08 / 100	1316 ms	87240 KiB

triples

#include "triples.h"
#include<bits/stdc++.h>

using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
typedef long long int lld;
int h[1000000];
int n;
vector<int> Pts[1000000];
set<int> S[1000000];
bool test(int a, int b, int c){
  if(0<=a && a<b && b<c && c<n){
    vector<int> X={b-a,c-a,c-b};
    sort(X.begin(),X.end());
    vector<int> Y={h[a],h[b],h[c]};
    sort(Y.begin(),Y.end());
    rep(i,0,3){
      if(X[i]!=Y[i])return false;
    }
    // cout<<a<<" "<<b<<" "<<c<<endl;
    return true;
  }return false;
}
long long count_triples(std::vector<int> H) {
  
  
  
  lld ans=0;
  n=H.size();
  rep(i,0,n)h[i]=H[i];
  rep(i,0,3*n)S[i].clear(),Pts[i].clear();
  
  // lld ans2=0;
  // rep(a,0,n){
    // rep(b,a+1,n){
      // rep(c,b+1,n){
        // int res=test(a,b,c);
        // ans2+=res;
      // }
    // }
  // }
  
  
  
  rep(i,0,n){
    int Nx=i+H[i];
    if(Nx<n){
      ans+=test(i,i+H[Nx],Nx);
      if(i+H[Nx]!=Nx-H[Nx]){
        ans+=test(i,Nx-H[Nx],Nx);
      }
    }
  }
  rep(i,0,n){
    int Pr=i-H[i];
    if(Pr>=0){
      ans+=test(Pr,Pr+H[Pr],i);
      if(Pr+H[Pr]!=i-H[Pr]){
        ans+=test(Pr,i-H[Pr],i);
      }
    }
  }
  
  rep(i,0,n){
    int Nx=i+H[i];
    if(H[Nx]!=2*H[i]){
      ans+=test(i,Nx,i+H[Nx]);
    }
  }
  
  // vector<pair<int,int> >P;
  rep(i,0,n){
    int X=i-H[i]+n;
    int Y=i+H[i]+n;
    if(0<=X && X<3*n && 0<=Y && Y<3*n)Pts[X].push_back(Y);
  }
  
  // int A=0;
  // trav(a,P){
    // trav(b,P){
      // trav(c,P){
        // if(a!=b && b!=c && a!=c){
          // if(b.first==a.first && b.second==c.second && a.second==c.first){
            // A++;
            // cout<<"2 "<<(a.first+a.second)/2<<" "<<(b.first+b.second)/2<<" "<<(c.first+c.second)/2<<endl;
          // }
        // }
      // }
    // }
  // }
  // cout<<A<<endl;
  
  rep(i,0,3*n){
    trav(a,Pts[i]){
      if(S[i].size()<S[a].size()){
        trav(b,S[i]){
          ans+=(S[a].find(b)!=S[a].end());
        }
      }else{
        trav(b,S[a]){
          ans+=(S[i].find(b)!=S[i].end());
        }
      }
    }
    
    trav(a,Pts[i]){
      S[a].insert(i);
    }
  }
  // cout<<ans<<" "<<ans2<<endl;
  return ans;
}

bool isprime(int x){
  for(int i=2;i*i<=x;i++){
    if(x%i==0)return false;
  }
  return true;
}

std::vector<int> construct_range(int M, int K) {
  
  lld sq=1;
  while(true){
    if(4*(sq+1)*(sq+1)>M)break;
    sq++;
  }
  while(!isprime(sq)){
    sq--;
  }
  vector<int> V;
  for(lld i=0;i<sq;i++){
    int u=(i*i)%sq;
    u=sq-u;
    u%=sq;
    V.push_back(i+2*sq*u);
  }
  sort(V.begin(),V.end());
  vector<int> V2;
  vector<int> sol(M,1);
  rep(i,0,M){
    if(i%2==0)sol[i]=1;
    else sol[i]=2;
  }
  // cerr<<V.size()<<endl;
  rep(i,0,V.size()){
    rep(j,i+1,V.size()){
      V2.push_back(V[i]+V[j]);
      sol[V[i]+V[j]]=(V[j]-V[i]);
      
      
    }
  }
  
  sort(V2.begin(),V2.end());
  rep(i,1,V2.size()){
    assert(V2[i]!=V2[i-1]);
    // assert(V2[i]!=V2[i-1]+1);
  }
  
  
  
  // cout<<1<<endl;
  return sol;
}

• 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: 1.3333 / 5
• Subtask 8: 0.9025 / 5
• Subtask 9: 0.6478 / 5
• Subtask 10: 0.7351 / 5
• Subtask 11: 1.6701 / 5
• Subtask 12: 0.7892 / 5