Submission #1257315

#TimeUsernameProblemLanguageResultExecution timeMemory
1257315biankTriple Peaks (IOI25_triples)C++20
100 / 100
579 ms32436 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...