Submission #1250895

#TimeUsernameProblemLanguageResultExecution timeMemory
1250895lukameladzeTriple Peaks (IOI25_triples)C++20
75.29 / 100
116 ms16964 KiB
#pragma GCC optimize("Ofast") #pragma GCC optimize ("O3") #pragma GCC optimization ("unroll-loops") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma") #include "triples.h" #include <vector> #include <algorithm> #include <cstdio> #include <cassert> #include <iostream> #include <cmath> #define pb push_back using namespace std; int check(int i, int j, int k, vector<int>& h) { int x = h[i]; int y = h[j]; int z = h[k]; if (x > y) swap(x, y); if (y > z) swap(y, z); if (x > z) swap(x, z); if (x == j - i && y == k - j && z == k - i) return 1; if (x == k - j && y == j - i && z == k - i) return 1; return 0; } long long count_triples(std::vector<int> H) { int n = H.size(); long long ans = 0; vector <int> h(n); for (int i = 0; i < n; i++) { h[i] = H[i]; // cout<<h[i]<<" "; } // cout<<"\n"; for (int i = 0; i < n; i++) { int k = h[i] + i; if (k <= i + 1 || k >= n) continue; int j = h[k] + i; if (j > i && j < k) { ans += check(i, j, k, h); } int j2 = k - h[k]; if (j2 > i && j2 < k && j2 != j) { ans += check(i, j2, k, h); } } for (int k = 0; k < n; k++) { int i = k - h[k]; if (i < 0 || i >= k) continue; int j = h[i] + i; if (j > i && j < k) { ans += check(i, j, k, h); } int j2 = k - h[i]; if (j2 > i && j2 < k && j2 != j) { ans += check(i, j2, k, h); } } for (int i = 0; i < n; i++) { int j = h[i] + i; int k = h[j] + i; // cout << "i: " << i << ", j: " << j << ", k: " << k << " " << check(i, j, k, h) << "\n"; if (j < i + 1 || j > n) continue; if (k > j && k < n) { ans += check(i, j, k, h); } } // for (int i = 0; i < n; i++) { // for (int j = i + 1; j < n; j++) { // for (int k = j + 1; k < n; k++) { // if (check(i, j, k, h) && k - i == h[j] && h[i] == j - i && h[k] == k - j) { // res++; // cout << "i: " << i << ", j: " << j << ", k: " << k << "\n"; // } // } // } // } // cout << "res: " << res << "\n"; // cout << "ans: " << ans << "\n"; vector <vector<int>> vec(2 * n + 1); for (int i = 0; i < n; i++) { vec[h[i] - i + n].pb(i); } int b = 400; for (int dif = 0; dif <= 2 * n; dif++) { if (vec[dif].size() < b) { for (int idi = 0; idi < vec[dif].size(); idi++) { for (int idj = idi + 1; idj < vec[dif].size(); idj++) { int i = vec[dif][idi]; int j = vec[dif][idj]; int k = h[j] + i; if (k > j && k < n && h[j] == k - i && h[i] != h[k]) { ans += check(i, j, k, h); } } } } else { int act = dif - n; for (int k = 2; k < n; k++) { int i2 = k - h[k] - act; if (i2 < 0 || i2 % 2) continue; int i = i2 / 2; if (i < 0 || i >= n) continue; int j = h[k] + i; if (j > i && j < k && h[j] == k - i && h[i] != h[k]) { ans += check(i, j, k, h); } } } } return ans; } std::vector<int> construct_range(int M, int K) { vector <int> v; for (int i = 0; i < M; i++) { if (i % 3 == 0) v.pb(2); else v.pb(1); } return v; }
#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...