Submission #1263110

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263110		nerrrmin	Triple Peaks (IOI25_triples)	C++20	16.29 / 100	15 ms	3516 KiB

triples

#include "triples.h"
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn = 2e5 + 10;
int n;
long long a[maxn];
long long count_triples(std::vector<int> H)
{
    n = H.size();
    for (int i = 1; i <= n; ++ i)
    {
        a[i] = H[i-1];
    }
    long long ans = 0;

    for (int j = 3; j <= n; ++ j)
    {
        long long dist = a[j];
        int i = j - dist;
        if(!(i >= 1 && i <= n))continue;
        int mdist = a[i];
        if(mdist > (dist - mdist))continue;
        int pos1 = i + mdist, is = 0;
        if(pos1 < j && a[pos1] == j - pos1)
        {
            ans ++;
            is = 1;
        }
        pos1 = j - mdist;
        if(pos1 == i + mdist && is)continue;
        if(pos1 > i && a[pos1] == pos1 - i)ans ++;
    }
    return ans;
    for (int i = 1; i <= n; ++ i)
    {
        for (int j = i + 2; j <= n; ++ j)
        {
            int dist = j - i;
            if(a[i] == dist || a[j] == dist)
            {
                int other = a[i] + a[j] - dist;
                int pos = i + other;
                int is = 0;
                if(i < pos && pos < j && a[pos] == j - pos)
                {
                    is = 1;
                    ans ++;
                }
                pos = j - other;
                if(is && pos == i + other)continue;
                if(i < pos && pos < j && a[pos] == pos - i)ans ++;
            }
            else
            {
                if(a[i] + a[j] == dist)
                {
                    int pos = i + a[i];
                    int is = 0;
                    if(i < pos && pos < j && a[pos] == dist)
                    {
                        is = 1;
                        ans ++;
                    }
                    pos = j - a[i];
                    if(is && pos == i + a[i])continue;
                    if(i < pos && pos < j && a[pos] == dist)ans ++;
                }
            }
        }
    }
    return ans;
}

std::vector<int> construct_range(int M, int K) {
    vector < int > s;
    s.pb(1);
    s.pb(2);
    s.pb(1);
    for (int i = 3; i <= M; ++ i)
        s.pb(i);
    while(s.size() > M)s.pop_back();
  return s;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 0 / 6
• Subtask 3: 0 / 10
• Subtask 4: 11 / 11
• Subtask 5: 0 / 16
• Subtask 6: 0 / 19
• Subtask 7: 3 / 5
• Subtask 8: 1.245 / 5
• Subtask 9: 0.4998 / 5
• Subtask 10: 0.2143 / 5
• Subtask 11: 0.25 / 5
• Subtask 12: 0.0833 / 5