Submission #1249808

#TimeUsernameProblemLanguageResultExecution timeMemory
1249808QwertyPiTriple Peaks (IOI25_triples)C++20
21.69 / 100
1624 ms16000 KiB
#include "triples.h" #include <bits/stdc++.h> #define int long long using namespace std; const int N_MAX = 2e5 + 11; int N; int H[N_MAX]; bool in(int x) { return 0 <= x && x < N; } bool check(int a, int b, int c) { if (!in(a) || !in(b) || !in(c) || a >= b || b >= c) return false; return multiset<int>{H[a], H[b], H[c]} == multiset<int>{abs(a - b), abs(a - c), abs(b - c)}; } int ans = 0; set<tuple<int, int, int>> S; bool check_set(int a, int b, int c) { bool ok = check(a, b, c); if (!ok) return false; if (S.count({a, b, c})) return false; S.insert({a, b, c}); ans++; return true; } int count_triples(vector<int32_t> H) { N = H.size(); for (int i = 0; i < N; i++) ::H[i] = H[i]; for (int i = 0; i < N; i++) { int a = i; { int b = a - H[a]; if (in(b)) { int c = b + H[b]; check_set(b, a, c); } if (in(b)) { int c = a + H[b]; check_set(b, a, c); } } { int b = a + H[a]; if (in(b)) { int c = b - H[b]; check_set(c, a, b); } if (in(b)) { int c = a - H[b]; check_set(c, a, b); } } } for (int a = 0; a < N; a++) { for (int c = a + 2; c < a + 30; c++) { check_set(a, a + H[a], c); check_set(a, a + H[c], c); } } return ans; } vector<int32_t> construct_range(int32_t M, int32_t _K) { const int K = sqrt(M); M = M / K * K - 1; vector<int32_t> ans(M); int B = M / K; for (int i = 0; i < B; i++) { for (int j = 0; j < K; j++) { ans[i * K + j] = K * (B - 1 - i) + 1 + j; } } for (int j = 0; j < K - 1; j++) { ans[B * K + j] = K - 1 - j; } // cout << "ANS = " << count_triples(ans) << endl; 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...