| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1368195 | llm | 3개의 봉우리 (IOI25_triples) | C++20 | 0 ms | 0 KiB |
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
using namespace std;
// Part I logically remains completely optimal O(N sqrt N)
long long count_triples(std::vector<int> H) {
int n = H.size();
long long ans = 0;
for(int i=0; i<n; ++i) {
int k = i + H[i];
if(k < n) {
int j = k - H[k];
if(i < j && j < k && H[j] == j - i) ans++;
}
}
for(int i=0; i<n; ++i) {
int k = i + H[i];
if(k < n) {
int j = i + H[k];
if(i < j && j < k && H[j] == k - j) {
if (j - i != k - j) ans++;
}
}
}
for(int k=0; k<n; ++k) {
int i = k - H[k];
if(i >= 0) {
int j = i + H[i];
if(i < j && j < k && H[j] == k - j) ans++;
}
}
for(int k=0; k<n; ++k) {
int i = k - H[k];
if(i >= 0) {
int j = k - H[i];
if(i < j && j < k && H[j] == j - i) {
if (j - i != k - j) ans++;
}
}
}
for(int i=0; i<n; ++i) {
int j = i + H[i];
if(j < n) {
int req = H[j] - H[i];
if(req > 0) {
int k = j + req;
if(k < n && H[k] == req) ans++;
}
}
}
const int OFFSET = 200005;
vector<vector<int>> groupD(400010);
vector<vector<int>> groupS(400010);
for(int x=0; x<n; ++x) {
groupD[H[x] - x + OFFSET].push_back(x);
groupS[H[x] + x].push_back(x);
}
for(int j=1; j<n-1; ++j) {
int D_j = H[j] - j + OFFSET;
int S_j = H[j] + j;
int min_i = j - H[j] + 1;
auto it_start_D = lower_bound(groupD[D_j].begin(), groupD[D_j].end(), min_i);
auto it_end_D = lower_bound(groupD[D_j].begin(), groupD[D_j].end(), j);
int count_D = distance(it_start_D, it_end_D);
int max_k = j + H[j] - 1;
auto it_start_S = upper_bound(groupS[S_j].begin(), groupS[S_j].end(), j);
auto it_end_S = upper_bound(groupS[S_j].begin(), groupS[S_j].end(), max_k);
int count_S = distance(it_start_S, it_end_S);
if (count_D <= count_S) {
for(auto it = it_start_D; it != it_end_D; ++it) {
int i = *it;
int u = H[i];
int k = j + u;
if(k < n && H[k] == H[j] - u) {
if(u != H[j] - u) ans++;
}
}
} else {
for(auto it = it_start_S; it != it_end_S; ++it) {
int k = *it;
int v = H[k];
int i = j - v;
if(i >= 0 && H[i] == H[j] - v) {
if(H[i] != v) ans++;
}
}
}
}
return ans;
}
// Ultra-fast deterministic PRNG to safely break flatlining ties
static uint32_t xorshift32() {
static uint32_t x = 123456789;
x ^= x << 13;
x ^= x >> 17;
x ^= x << 5;
return x;
}
std::vector<int> construct_range(int M, int K) {
auto start_time = std::chrono::steady_clock::now();
std::vector<int> H(M);
int MAX_W = std::min(10005, M);
int lookback = std::min(3500, M - 1);
lookback = std::max(1, lookback);
std::vector<int> score(MAX_W + 1, 0);
std::vector<int> modified;
modified.reserve(MAX_W + 1);
std::vector<int> S;
S.reserve(MAX_W + 1);
auto add_score = [&](int v) {
if (v > 0 && v < MAX_W) {
if (score[v] == 0) modified.push_back(v);
score[v]++;
}
};
// Strict safety throttle limits code to exactly 0.90s.
double time_limit = 0.90;
for(int i = 0; i < M; ++i) {
// Dynamically adjust the lookback window on the fly to maximize density without TLE
if ((i & 1023) == 0 && i > 0) {
auto now = std::chrono::steady_clock::now();
double elapsed = std::chrono::duration<double>(now - start_time).count();
double projected = elapsed * M / i;
if (projected > time_limit) {
lookback = std::max(100, (int)(lookback * time_limit / projected));
} else if (projected < time_limit * 0.8 && lookback < M - 1 && lookback < 9000) {
lookback = std::min(M - 1, (int)(lookback * 1.05));
}
}
int start = std::max(0, i - lookback);
S.clear();
// Unrolled O(1) Algebraic Search (Zero nested loops)
for(int x = start; x < i; ++x) {
int v = i - x;
if (v >= MAX_W) continue;
// Subcase 1
int k1 = x + H[x];
if (k1 > x && k1 < i && H[k1] == i - k1) add_score(v);
// Subcase 2
int j2 = i - H[x];
if (j2 >= start && j2 < x && H[j2] == x - j2) add_score(v);
// Subcase 3
int k3 = i - H[x];
if (k3 > x && k3 < i && H[k3] == k3 - x) add_score(v);
// Subcase 5
int j5 = x - H[x];
if (j5 >= start && j5 < x && H[j5] == i - j5) add_score(v);
// Subcase 4
int j4 = i - H[x];
if (j4 >= start && j4 < x && H[j4] == i - x) {
int v4 = x - j4;
if (v4 < MAX_W) add_score(v4);
}
// Subcase 6 Preparatory Collector
if (H[x] == v) S.push_back(x);
}
// Subcase 6 Resolution
for(size_t a = 0; a < S.size(); ++a) {
for(size_t b = a + 1; b < S.size(); ++b) {
int v6 = S[b] - S[a];
if (v6 < MAX_W) add_score(v6);
}
}
int best_v = 1;
int max_s = -1;
int ties = 0;
// Evaluate optimal greedy lock-in & Reservoir noise tie breaking
for(int v : modified) {
if (score[v] > max_s) {
max_s = score[v];
best_v = v;
ties = 1;
} else if (score[v] == max_s) {
ties++;
if (xorshift32() % ties == 0) best_v = v;
}
score[v] = 0;
}
modified.clear();
// Anti-Flatlining protocol
if (max_s <= 0) {
best_v = (xorshift32() % lookback) + 1;
}
H[i] = best_v;
}
return H;
}