Submission #1255606

#TimeUsernameProblemLanguageResultExecution timeMemory
1255606WeIlIaNTriple Peaks (IOI25_triples)C++20
72.03 / 100
2095 ms211940 KiB
#include "triples.h" #include <bits/stdc++.h> using namespace std; #define MOD1 1000000007 #define MOD2 998244353 #define fir first #define sec second #define pushf push_front #define pushb push_back #define popf pop_front #define popb pop_back #define mp make_pair #define all(a) a.begin(), a.end() #define FOR1(a) for (int _ = 0; _ < a; ++_) #define FOR2(i, a) for (int i = 0; i < a; ++i) #define FOR3(i, a, b) for (int i = a; i < b; ++i) #define RFOR1(a) for (int _ = (a)-1; _ >= 0; --_) #define RFOR2(i, a) for (int i = (a)-1; i >= 0; --i) #define RFOR3(i, a, b) for (int i = (b)-1; i >= a; --i) #define overload3(a, b, c, d, ...) d // Always choose the fourth argument to call. Hence, which function to call is determined by the number of given arguments. #define REP(...) overload3(__VA_ARGS__, FOR3, FOR2, FOR1)(__VA_ARGS__) #define RREP(...) overload3(__VA_ARGS__, RFOR3, RFOR2, RFOR1)(__VA_ARGS__) typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; typedef pair<ll, ll> pll; typedef vector<ll> vll; typedef vector<bool> vb; typedef vector<char> vc; typedef vector<string> vs; typedef vector<pii> vpii; typedef vector<pll> vpll; typedef vector<vi> vvi; typedef vector<vll> vvll; typedef vector<vb> vvb; typedef vector<vc> vvc; typedef vector<vpii> vvpii; typedef vector<vpll> vvpll; typedef queue<int> qi; typedef queue<ll> qll; typedef queue<pii> qpii; typedef queue<pll> qpll; typedef deque<int> dqi; typedef deque<ll> dqll; typedef deque<pii> dqpii; typedef deque<pll> dqpll; typedef priority_queue<int> pqi; typedef priority_queue<ll> pqll; typedef priority_queue<pii> pqpii; typedef priority_queue<pll> pqpll; typedef priority_queue<int, vi, greater<int> > r_pqi; typedef priority_queue<ll, vll, greater<ll> > r_pqll; typedef priority_queue<pii, vpii, greater<pii> > r_pqpii; typedef priority_queue<pll, vpll, greater<pll> > r_pqpll; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); unordered_map<int, int> rec; int cnt, deg[300001], vis[300001]; vpii Map[300001]; vector<array<int, 3>> vec; ll count_triples(vi H) { int n = H.size(); // cases of {Hi, Hj, Hk} REP(i, n) { int j = H[i] + i; if (j < n) { // = {j-i, k-j, k-i} int k = H[j] + j; if (k < n) { vec.pushb({i, j, k}); } // = {j-i, k-i, k-j} k = H[j] + i; if (k < n) { vec.pushb({i, j, k}); } } } REP(i, n) { int k = H[i] + i; if (k < n) { // = {k-i, j-i, k-j} int j = k - H[k]; if (0 <= j) vec.pushb({i, j, k}); // = {k-i, k-j, j-i} j = H[k] + i; if (j < n) { vec.pushb({i, j, k}); } } } REP(j, n) { int i = j - H[j]; if (0 <= i) { // = {k-j, j-i, k-i} int k = H[i] + j; if (k < n) { vec.pushb({i, j, k}); } } } // = {k-j, k-i, j-i} REP(i, n) { // discretize int u = i - H[i], v = i + H[i]; if (!rec.count(u)) rec[u] = cnt++; if (!rec.count(v)) rec[v] = cnt++; deg[rec[u]]++; deg[rec[v]]++; } REP(i, n) { int u = rec[i - H[i]], v = rec[i + H[i]]; if (deg[u] > deg[v] || (deg[u] == deg[v] && u > v)) swap(u, v); Map[u].pushb(mp(v, i)); } fill(vis, vis+cnt, -1); REP(u, cnt) { for (auto [v, a] : Map[u]) vis[v] = a; for (auto [v, a] : Map[u]) for (auto [w, b] : Map[v]) if (~vis[w]) vec.pushb({a, b, vis[w]}); for (auto [v, a] : Map[u]) vis[v] = -1; } for (auto &each : vec) sort(all(each)); sort(all(vec)); vec.erase(unique(all(vec)), vec.end()); int ans = 0; for (auto &[i, j, k] : vec) { array<int, 3> a{j - i, k - i, k - j}, b{H[i], H[j], H[k]}; sort(all(a)); sort(all(b)); if (a == b) { ++ans; } } return ans; } vi construct_range(int M, int K) { vi ans; int sc = -1; double st = clock(); while((clock() - st) / CLOCKS_PER_SEC < 1.9) { vi seq; uniform_int_distribution<int> dist(1, M/2); REP(i, M) { seq.push_back(dist(rng)); } int ns = count_triples(seq); if(ns > sc) { sc = ns; ans = seq; } } return ans; }
#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...