Submission #1252124

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252124		idiotcomputer	Triple Peaks (IOI25_triples)	C++20	70 / 100	616 ms	48944 KiB

triples

//IOI 2025 Day 1 Problem B 

#include <bits/stdc++.h>
using namespace std;
#define ll long long int 
#define pb push_back
#define sz(x) (int) (x).size()
#define vi vector<int>
#define f first
#define s second 
#include "triples.h"


bool same(int a1, int a2, int a3, int b1, int b2, int b3){
    vi a(3);
    vi b(3);
    a[0] = a1, a[1] = a2, a[2] = a3, b[0] = b1, b[1] = b2, b[2] = b3;
    sort(a.begin(), a.end()), sort(b.begin(),b.end());
    for (int i = 0; i < 3; i++) if (a[i] != b[i]) return 0;
    return 1;
}

long long count_triples(vi h){

    int n = sz(h);

    ll res = 0;
    for (int i = 0; i < n; i++){
        //largest right
        if (h[i] > i) continue;
        int c = h[i-h[i]];
        //int o1 = res;
        if (c < h[i]){
            if (h[i-h[i]+c] == h[i] - c) res++;
            if (c+c != h[i] && h[i-c] == h[i] - c) res++;
        }
        //if (res > o1) cout << i << " 1 " << h[i] << ' ' << c << ' ' << i-h[i] << '\n';
        //o1 = res;
        //largest center, right is right 
        c = h[i-h[i]];
        if (c > h[i] && c <= i && h[i-c] == c - h[i]) res++;  
        //if (res > o1) cout << i << " 2 " << h[i] << ' ' << c << ' ' << i-h[i] << '\n';
    }
    //cout << res << '\n';
    for (int i = 0; i < n; i++){
        //largest left
        if (h[i]+i >= n) continue;
        int c = h[i+h[i]];
        if (c < h[i]){
            if (h[i+h[i]-c] == h[i]-c) res++;
            if (c+c != h[i] && h[i+c] == h[i]-c) res++;
        }
    }
    //cout << res << '\n';
    //cout << res << '\n';
    //largest center, left is right and right is left
    //i-h[i], i+h[i]
    set<int> lef[2*n];
    set<int> rig[2*n];

    for (int i = 0; i < n; i++) rig[h[i]+i].insert(i);
    for (int i = 0; i < n; i++){
        rig[h[i]+i].erase(i);
        int i1 = i-h[i]+n;
        int i2 = h[i]+i;
       // cout << i << " " << i1 << " " << i2 << '\n';
        if (sz(lef[i1]) < sz(rig[i2])){
            //cout << "Checkign left\n";
            for (int j : lef[i1]) if (i+h[j] < n && h[i+h[j]] == h[i] - h[j] && h[j] * 2 != h[i]) res++;
        } else {
            //cout << "Checking right " << *rig[i2].begin() << '\n';
            for (int j : rig[i2]) if (i-h[j] >= 0 && h[i-h[j]] == h[i] - h[j] && h[j] * 2 != h[i]) res++;
        }
        lef[i1].insert(i);
    }
    

    /*ll c1 = 0;
    for (int i = 0; i < n; i++) for (int j = i+1; j < n; j++){
        int v1 = h[i];
        int v2 = h[j];
        if (v1 > v2) swap(v1,v2);
        //missing longest
        int c2 = c1;
        if (i + v1 + v2 < n) c1 += same(v1,v2,h[i+v1+v2],j-i,i+v1+v2-j,v1+v2);
        //v2 is longest
        if (i+v2 < n) c1 += same(v1,v2,h[i+v2],j-i,i+v2-j,v2);
        if (c1> c2) cout << i << " " << j << " " << v1 << " " << v2 << "\n";
    }   
    cout << c1 << '\n';*/
    return res;
}

vi construct_range(int m, int k){
    return {};
}

/*
namespace {

void run_part1() {
  int N;
  assert(1 == scanf("%d", &N));
  std::vector<int> H(N);
  for (int i = 0; i < N; i++)
    assert(1 == scanf("%d", &H[i]));
  fclose(stdin);

  long long T = count_triples(H);

  printf("%lld\n", T);
  fclose(stdout);
}

void run_part2() {
  int M, K;
  assert(2 == scanf("%d %d", &M, &K));
  fclose(stdin);

  std::vector<int> H = construct_range(M, K);

  int N = H.size();
  printf("%d\n", N);
  for (int i = 0; i < N; i++)
    printf("%d%c", H[i], " \n"[i + 1 == N]);
  fclose(stdout);
}

} // namespace

int main() {
  int part;
  assert(1 == scanf("%d", &part));
  if (part == 1)
    run_part1();
  else if (part == 2)
    run_part2();

  return 0;
}
*/

• 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: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5