Submission #1253270

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253270		daniel920712	Triple Peaks (IOI25_triples)	C++20	29 / 100	46 ms	2632 KiB

triples

#include "triples.h"
#include <map>
#include <set>
using namespace std;
map < int , int > con;
set < int > can;
vector < int > tt;
int N;
int check(int a, int b,int c,int x,int y,int z)
{
    return a==x&&b==y&&c==z;
}
int check2(int a,int b,int c)
{
    if(c<a||c<b||c>=N) return 0;
    int x=tt[a];
    int y=tt[b];
    int z=tt[c];
    if(x>y) swap(x,y);
    if(y>z) swap(y,z);
    if(x>y) swap(x,y);
    return check(min(b-a,c-b),max(b-a,c-b),c-a,x,y,z);
}
long long count_triples(std::vector<int> H)
{
    long long ans=0;
    int i,j,k,x,y,z;
    N=H.size();
    tt=H;
    if(N<=5000)
    {
        for(i=0;i<N;i++)
        {
            for(j=i+1;j<N;j++)
            {
                can.clear();
                if(check2(i,j,i+tt[i])) can.insert(i+tt[i]);
                if(check2(i,j,i+tt[j])) can.insert(i+tt[j]);

                if(check2(i,j,j+tt[i])) can.insert(j+tt[i]);
                if(check2(i,j,j+tt[j])) can.insert(j+tt[j]);
                ans+=(long long) can.size();
            }
        }
    }
    else
    {
        for(i=0;i<N;i++)
        {
            x=i-tt[i];
            if(x>=0)
            {
                y=x+tt[x];
                z=i-tt[x];

                if(check2(x,y,i)) ans++;
                if(z!=y&&check2(x,z,i)) ans++;
            }
            /*for(j=i+1;j<=i+10&&j<N;j++)
            {
                for(k=j+1;k<=i+10&&k<N;k++) if(check2(i,j,k)) ans++;
            }*/
        }
    }
    return ans;
}

std::vector<int> construct_range(int M, int K) {
  return {1, 1, 1};
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 0 / 6
• Subtask 3: 10 / 10
• Subtask 4: 11 / 11
• Subtask 5: 0 / 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