Submission #1250788

#TimeUsernameProblemLanguageResultExecution timeMemory
1250788s4dzTriple Peaks (IOI25_triples)C++20
26 / 100
2096 ms33096 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; //sub4: vector<int> construct_range(int M, int K) { vector<int> ans1 = { 4, 3, 1, 2, 1, 4, 3, 2, 7, 6, 5, 8, 11, 10, 9, 1, 7, 2, 3, 4, }; if(M <= 20){ while(ans1.size() > M || ans1.back() >= M) ans1.pop_back(); return ans1; } vector<int> S = {0}; vector<bool> in_span(2*M, false); int span_cnt = 0; vector<pair<int,int>> pts; while(span_cnt < M-1) { int best_t = -1, best_gain = -1; vector<bool> inS(2*M, false); for(int u:S) inS[u] = true; for(int t = 0; t <= 2*(M-1); t += 2) if(!inS[t]) { int gain = 0; for(int u:S) { if(u==t) continue; int s = u + t; if(s >= 2 && s <= 2*(M-1) && (s%2==0) && !in_span[s]) ++gain; } if(gain > best_gain) { best_gain = gain; best_t = t; } } if(best_t < 0) break; for(int u:S) { if(u == best_t) continue; int s = u + best_t; if(s >= 2 && s <= 2*(M-1) && (s%2==0) && !in_span[s]) { int x = min(u, best_t), y = max(u, best_t); pts.emplace_back(x, y); in_span[s] = true; ++span_cnt; } } S.push_back(best_t); } vector<int> H(M, 1); for(auto [x,y] : pts) { int idx = (x + y) / 2; int h = (y - x) / 2; if(idx >= 0 && idx < M) { H[idx] = h; } } return H; } /*long long count_triples(vector<int> H) { int n = H.size(); ll ans = 0; for (int k = 0; k < n; k++) { int c = H[k]; int i = k - c; if (i < 0 || i >= n) continue; int a = H[i]; if (a > c - a) continue; int need = c - a; int j1 = i + a; int j2 = k - a; if (i < j1 && j1 < k && H[j1] == need) ans++; if (j2 != j1 && i < j2 && j2 < k && H[j2] == need) ans++; } return ans; }*/ /*void nen(vector<int>& H) { vector<int> temp = H; sort(temp) }*/ long long count_thdb(vector<signed> H) { int n = H.size(); vector<int> u(n), v(n); for(int i = 0; i < n; i++) { u[i] = i - H[i]; v[i] = i + H[i]; } } long long count_triples(vector<int> H) { int n = H.size(); long long count = 0; for (int i = 0; i < n; i++) { long long k = (long long)i + H[i]; if (k < n) { if (H[i] > H[k]) { int diff = H[i] - H[k]; int j1 = i + diff; int j2 = i + H[k]; if (j1 > i && j1 < k && H[j1] == diff) { count++; } if (j2 > i && j2 < k && j2 != j1 && H[j2] == diff) { count++; } } } } for (int k = 0; k < n; k++) { long long i0 = (long long)k - H[k]; if (i0 >= 0) { if (H[k] > H[i0]) { int diff = H[k] - H[i0]; int j1 = i0 + H[i0]; int j2 = k - H[i0]; if (j1 > i0 && j1 < k && H[j1] == diff) { count++; } if (j2 > i0 && j2 < k && j2 != j1 && H[j2] == diff) { count++; } } } } int MAXS = 2 * n + 10; vector<vector<int>> list_A(MAXS + 1); vector<vector<int>> list_sum(MAXS + 1); for (int i = 0; i < n; i++) { long long s = (long long)i + H[i]; if (s <= MAXS) { list_A[s].push_back(i); } } for (int k = 0; k < n; k++) { long long s = (long long)k + H[k]; if (s <= MAXS) { list_sum[s].push_back(k); } } int B = sqrt(n); for (int j = 0; j < n; j++) { long long s = j; if (s <= MAXS) { for (int i : list_A[s]) { if (i < j) { long long k_val = (long long)i + H[j]; if (k_val < n) { if (H[j] > H[i] && H[k_val] == H[j] - H[i]) { count++; } } } } } long long s0 = (long long)j + H[j]; if (s0 > MAXS) continue; long long low_bound = max((long long)j + 1, (long long)H[j]); long long high_bound = min((long long)n - 1, (long long)j + H[j] - 1); if (low_bound > high_bound) continue; vector<int>& L = list_sum[s0]; if (L.empty()) continue; if (L.size() <= (size_t)B) { for (int k_val : L) { if (k_val < low_bound) continue; if (k_val > high_bound) break; int i_val = k_val - H[j]; if (H[i_val] == k_val - j) { count++; } } } else { for (int k_val = low_bound; k_val <= high_bound; k_val++) { if (k_val + H[k_val] == s0) { int i_val = k_val - H[j]; if (i_val >= 0 && i_val < j && H[i_val] == k_val - j) { count++; } } } } } return count; }

Compilation message (stderr)

triples.cpp: In function 'long long int count_thdb(std::vector<int>)':
triples.cpp:97:1: warning: no return statement in function returning non-void [-Wreturn-type]
   97 | }
      | ^
#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...