#include "triples.h"
#include <bits/stdc++.h>
using namespace std;
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
using vi = vector<int>;
using ll = long long;
#define fst first
#define snd second
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define pb push_back
#define eb emplace_back
ll count_triples(vi h) {
int n = sz(h);
vector<tuple<int, int, int>> triples;
forn(i, n) {
int j = i + h[i];
if (j >= n) continue;
{
int k = j + h[j];
if (k < n && h[k] == k - i) triples.eb(i, j, k);
}
{
int k = j + h[j] - h[i];
if (j < k && k < n && h[k] == k - j && h[i] != h[k]) triples.eb(i, j, k);
}
}
forn(j, n) {
int i = j - h[j];
if (i < 0) continue;
{
int k = j + h[i];
if (k < n && h[k] == k - i) triples.eb(i, j, k);
}
{
int k = j + h[i] - h[j];
if (j < k && k < n && h[k] == k - j) triples.eb(i, j, k);
}
}
forn(j, n) {
int k = j + h[j];
if (k >= n) continue;
int i = j - h[k];
if (i >= 0 && h[i] == k - i) triples.eb(i, j, k);
}
vector<vi> diag1(2 * n), diag2(2 * n);
forn(i, n) {
diag1[h[i] - i + n].pb(i);
diag2[h[i] + i].pb(i);
}
sort(all(triples));
triples.erase(unique(all(triples)), end(triples));
int ret = sz(triples);
forn(j, n) {
auto &iCandidates = diag1[h[j] - j + n];
auto &kCandidates = diag2[h[j] + j];
if (sz(iCandidates) < sz(kCandidates)) {
for (int i : iCandidates) {
int k = j + h[i];
if (k < n && j - i == h[k] && h[j] == k - i) ret++;
}
} else {
for (int k : kCandidates) {
int i = j - h[k];
if (i >= 0 && k - j == h[i] && h[j] == k - i) ret++;
}
}
}
return ret;
}
const int INF = 1e9;
vi construct_range(int M, int K) {
vi ret = {};
int best = 0;
int seed = -1247761304;
while (best < K) {
mt19937 rng(seed++);
int S = sqrt(6 * M);
S = uniform_int_distribution<int>(S * 2 / 3, S * 4 / 3 + 1)(rng);
set<int> s;
vi diag(S);
forn(i, S) {
diag[i] = uniform_int_distribution<int>(-M / 2, M * 3 / 2 + 1)(rng);
diag[i] /= 2, diag[i] *= 2;
if (s.count(diag[i])) i--;
else s.insert(diag[i]);
}
vi ans(M, INF);
forn(i, S) forsn(j, i + 1, S) {
int idx = (diag[i] + diag[j]) / 2;
int val = abs(diag[i] - diag[j]) / 2;
if (0 <= idx && idx < M && 1 <= val && val < M) ans[idx] = min(ans[idx], val);
}
forn(i, M) if (ans[i] == INF) {
ans[i] = uniform_int_distribution<int>(1, 2)(rng);
}
int triples = count_triples(ans);
if (triples > best) best = triples, ret = ans;
}
return ret;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |