Submission #1252806

#TimeUsernameProblemLanguageResultExecution timeMemory
1252806lrnnzTriple Peaks (IOI25_triples)C++20
51 / 100
2122 ms525184 KiB
#include <bits/stdc++.h> #include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <iomanip> #include <queue> #include <random> #include "triples.h" using namespace std; #define all(a) (a).begin(), (a).end() #define ll long long #define ld long double #define ui uint64_t #define cont(set, element) ((set).find(element) != (set).end()) #define pb push_back #define chmin(x, y) (x = min(x, y)) #define chmax(x, y) (x = max(x, y)) /********* DEBUG *********/ template <typename T> void outvec(const vector<T>& Z){ for (const T& x : Z) cout << x << ' '; cout << "\n"; } void printVariable(const any& var) { if (!var.has_value()) { cout << "null"; return; } if (var.type() == typeid(int)) { cout << any_cast<int>(var); } else if (var.type() == typeid(double)) { cout << any_cast<double>(var); } else if (var.type() == typeid(float)) { cout << any_cast<float>(var); } else if (var.type() == typeid(char)) { cout << any_cast<char>(var); } else if (var.type() == typeid(bool)) { cout << (any_cast<bool>(var) ? "true" : "false"); } else if (var.type() == typeid(string)) { cout << any_cast<string>(var); } else if (var.type() == typeid(const char*)) { cout << any_cast<const char*>(var); } else if (var.type() == typeid(long long)) { cout << any_cast<long long>(var); } else { cout << "[unknown type]"; } } template<typename... Args> void outval(Args... args) { vector<any> variables = {args...}; for (size_t i = 0; i < variables.size(); ++i) { printVariable(variables[i]); if (i != variables.size() - 1) { cout << " "; } } cout << "\n"; } /********* DEBUG *********/ #define sp << " " << #define fi first #define se second const ll MOD2 = 1e9 + 7; const ll MOD = 998244353; const ll inf = 1e18; ll count_triples(vector<int> H) { ll ans = 0, N = H.size(); map<ll, vector<ll>> seen; set<ll> done; // for hashing ll mult = 200001; auto add = [&](ll a, ll b, ll c) -> void { vector<ll> vec = {a,b,c}; sort(all(vec)); ll hsh = vec[0] + vec[1] * mult + vec[2] * mult * mult; done.insert(hsh); }; for (int i = 0; i < H.size(); i++){ // middle value is detached, 2 cases if (seen.count(i - H[i])){ for (auto &x : seen[i - H[i]]){ ll mid1 = x + H[x]; ll mid2 = x + H[i]; ll diff = i - x; if (mid1 < N && H[mid1] == diff){ add(x, i, mid1); } if (mid1 != mid2 && mid2 < N && H[mid2] == diff){ add(x, i, mid2); } } } seen[H[i] + i].pb(i); // GO FRONT ll frontIndex = H[i] + i; if (frontIndex < N){ ll middleIndex = frontIndex - H[frontIndex]; if (middleIndex >= 0 && middleIndex - H[middleIndex] == i){ add(i, middleIndex, frontIndex); } middleIndex = i + H[frontIndex]; if (middleIndex < N && middleIndex + H[middleIndex] == frontIndex){ add(i, middleIndex, frontIndex); } if (middleIndex < N && middleIndex - H[middleIndex] == frontIndex){ add(i, middleIndex, frontIndex); } ll moreFrontIndex = frontIndex + H[frontIndex]; if (moreFrontIndex < N && moreFrontIndex - H[moreFrontIndex] == i){ add(i, frontIndex, moreFrontIndex); } } ll backIndex = i - H[i]; if (backIndex < 0) continue; // go back immediately, 3 cases ll middleIndex = backIndex + H[backIndex]; if (middleIndex < N && middleIndex + H[middleIndex] == i){ add(i, middleIndex, backIndex); } middleIndex = i - H[backIndex]; if (middleIndex >= 0 && middleIndex - H[middleIndex] == backIndex){ add(i, middleIndex, backIndex); } if (middleIndex >= 0 && middleIndex + H[middleIndex] == backIndex){ add(i, middleIndex, backIndex); } // extend even more, 1 case ll moreBackIndex = backIndex - H[backIndex]; if (moreBackIndex >= 0 && moreBackIndex + H[moreBackIndex] == i){ add(i, backIndex, moreBackIndex); } } return done.size(); } std::vector<int> construct_range(int M, int K) { return {1, 1, 1}; }
#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...