Submission #1340445

#	Time	Username	Problem	Language	Result	Execution time	Memory
1340445		biblicaleagle	Triple Peaks (IOI25_triples)	C++20	Compilation error	0 ms	0 KiB

triples

#include "triples.h"

#include <map>
#include <unordered_set>
#include <algorithm>
#include <cmath>

using namespace std;

long long count_triples(vector<int> H) {
  vector<int> X, Y;
  for (int i=0; i < H.size(); i++) {
    X.push_back(i+H[i]);
    Y.push_back(i-H[i]);
  }
  
  set<int> supX = set<int>(X.begin(), X.end()); 

  map<int, vector<int>> invX;
  for (int i=0; i < H.size(); i++) invX[X[i]].push_back(i);

  unordered_set<long long> triples;
  const long long MULT = 1e6;

  for (int i=0; i < H.size(); i++) {
    int x = X[i], y = Y[i];

    if (x < H.size()) {
      int yx = Y[x];
      int xx = X[x];
      
      if (i < yx) {
        int yyx = Y[yx];
        if (yyx == i) triples.insert(i * MULT * MULT + yx * MULT + x);
      }
      
      if (xx < H.size()) {
        int yxx = Y[xx];
        if (yxx == i) triples.insert(i * MULT * MULT + x * MULT + xx);
      }

      int hx = H[x];
      if (i + hx < H.size()) {
        if (x == X[i + hx]) triples.insert(i * MULT * MULT + (i + hx) * MULT + x);
        if (x == Y[i + hx]) triples.insert(i * MULT * MULT + x * MULT + (i + hx));
      }
    }

    if (y >= 0) {
      int hy = H[y];
      if (i + hy < H.size()) {
        if (y == Y[i + hy]) triples.insert(y * MULT * MULT + i * MULT + (i + hy));
      }
    }  
  }
  
  for (int x : supX) {
    if (invX[x].size() < sqrt(H.size())) {
      for (int j: invX[x])
        for (int k: invX[x])
          if (j < k) {
            int yj = Y[j], yk = Y[k];
            if ((yk + yj) % 2 == 0) {
              int i = (yj + yk) / 2;
              if (i >= 0 && i < H.size()) 
                if (H[i] == (yk - yj) / 2) triples.insert(i * MULT * MULT + j * MULT + k);
            }
          }   
    } else {
      for (int i=0; i < H.size(); i++) {
        if ((x + X[i]) % 2 == 0 && (x + Y[i]) % 2 == 0) {
          int k = (x + X[i]) / 2, j = (x + Y[i]) / 2;
          if (i < j && k < H.size()) 
            if (X[j] == x && X[k] == x) triples.insert(i * MULT * MULT + j * MULT + k);
        }
      }
    }
  }

  return triples.size();
}

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

Compilation message (stderr)

triples.cpp: In function 'long long int count_triples(std::vector<int>)':
triples.cpp:17:3: error: 'set' was not declared in this scope
   17 |   set<int> supX = set<int>(X.begin(), X.end());
      |   ^~~
triples.cpp:7:1: note: 'std::set' is defined in header '<set>'; did you forget to '#include <set>'?
    6 | #include <cmath>
  +++ |+#include <set>
    7 | 
triples.cpp:17:7: error: expected primary-expression before 'int'
   17 |   set<int> supX = set<int>(X.begin(), X.end());
      |       ^~~
triples.cpp:57:16: error: 'supX' was not declared in this scope
   57 |   for (int x : supX) {
      |                ^~~~