Submission #1258635

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258635		nicolo_010	Triple Peaks (IOI25_triples)	C++20	100 / 100	1580 ms	40800 KiB

triples

#include "triples.h"
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using v = vector<T>;
using ll = long long;
using pii = pair<int, int>;
#define rep(i, k, n) for (int i = k; i < n; i++)
#define cerr if(0) cerr
#define cout if(0) cout

ll count_triangles(v<v<int>> &edges, v<v<int>> &adj) {
  ll cnt = 0;
  for (auto x : edges) {
    int u = x[0];
    int v = x[1];
    if (adj[u].size() > adj[v].size()) {
      swap(u, v);
    }
    int i, j;
    i=j=0;
    while (i < (int)adj[u].size() && j<(int)adj[v].size()) {
      if (adj[u][i] == adj[v][j]) {
        cnt++;
        i++; j++;
      }
      else if (adj[u][i] > adj[v][j]) j++;
      else i++;
    }
  }
  return cnt/3;
}

long long count_triples(std::vector<int> H) {
  ll ans=0;
  int N = H.size();
  rep(i, 0, N) {
    if (H[i]+i < N) {
      int k = H[i]+i;
      if (k-H[k] >= 0) {
        int j = k-H[k];
        if (H[i] == k-i && H[k] == k-j && H[j] == j-i && (i != j && j != k && k != i) && !(H[i] == k-i && H[k] == j-i && H[j] == k-j) && (i < j && j < k)) {
          ans++;
          cout << "1" << endl;
          cout << i << " " << j << " " << k << endl;
        }
      }
      if (H[k]+i < N) {
        int j = H[k]+i;
        if (H[i] == k-i && H[k] == j-i && H[j] == k-j && (i != j && j != k && k != i) && (i < j && j < k)) {
          ans++;
          cout << "2" << endl;
          cout << i << " " << j << " " << k << endl;
        }
      }
    }
  }
  rep(k, 0, N) {
    if (k-H[k] >= 0) {
      int i = k-H[k];
      if (H[i]+i < N) {
        int j = H[i]+i;
        if (H[k] == k-i && H[i] == j-i && H[j] == k-j && (i != j && j != k && k != i) && !(H[k] == k-i && H[i] == k-j && H[j] == j-i) && (i < j && j < k)) {
          ans++;
          cout << i << " " << j << " " << k << endl;
        }
      }
      if (k-H[i] >= 0) {
        int j = k-H[i];
        if (H[k] == k-i && H[i] == k-j && H[j] == j-i && (i != j && j != k && k != i) && (i < j && j < k)) {
          ans++;
          cout << i << " " << j << " " << k << endl;
        }
      }
    }
  }
  rep(i, 0, N) {
    if (H[i]+i < N) {
      int j = H[i]+i;
      if (H[j]+i < N) {
        int k = H[j]+i;
        if (H[i] == j-i && H[k] == k-j && H[j] == k-i && (i != j && j != k && k != i) && !(H[i] == k-j && H[k] == j-i && H[j] == k-i) && (i < j && j < k)) {
          ans++; 
          cout << i << " " << j << " " << k << endl;
        }
      } 
    }
  }
  unordered_map<int, int> mp;
  int id = 0;
  rep(i, 0, N) {
    if (!mp.count(i-H[i])) {
      mp[i-H[i]] = id++;
    }
    if (!mp.count(i+H[i])) {
      mp[i+H[i]] = id++;
    }
  }
  v<v<int>> edges;
  v<v<int>> adj(id);
  rep(i, 0, N) {
    edges.push_back({mp[i-H[i]], mp[i+H[i]]});
  }
  for (auto x : edges) {
    int u = x[0];
    int v = x[1];
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  for (auto &x : adj) {
    sort(x.begin(), x.end());
  }
  ans += count_triangles(edges, adj);
  //cout << fast_checker(H) << " ";
  return ans;
}

std::vector<int> construct_range(int M, int K) {
  int N = M;
  v<int> X = {-1}, Y = {1};
  v<int> used(2*N, 0), C = {0};
  v<int> H(N), V(2*N, -1e9);
  for (int i = 2; i < 2*N; i+=2) V[i] = 1;
  while (1) {
    auto it = max_element(V.begin(), V.end());
    int mx = *it, optimal = it-V.begin();
    cerr << optimal << " " << mx << endl;
    if (mx == 0) break;

    for (auto &x : C) {
      if (x+optimal < 2*N && !used[x+optimal]) {
        used[x+optimal] = 1;
        X.push_back(min(x, optimal));
        Y.push_back(max(x, optimal));
        for (auto &y : C) {
          int aux = x+optimal-y;
          if (0 <= aux && aux < 2*N) V[aux]--;
        } 
      }
    }

    for (int i=0; optimal+i < 2*N; i += 2) if (!used[optimal+i]) V[i]++;
    C.push_back(optimal);
    V[optimal] = -1e9;  
  }

  rep(i, 0, N) {
    H[(X[i]+Y[i])/2] = (Y[i]-X[i])/2;
  }
  ll cnt = count_triples(H);
  while (cnt < K) {
    rep(i, 0, N) {
      rep(j, 1, N) {
        int aux = H[i];
        H[i] = j;
        ll cntt = count_triples(H);
        if (cntt > cnt) cnt = cntt;
        else H[i] = aux;
      }
    }
  }
  return H;
}

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