제출 #1258487

#제출 시각아이디문제언어결과실행 시간메모리
1258487algoritTriple Peaks (IOI25_triples)C++17
56.29 / 100
2096 ms101132 KiB
#ifndef TRIPLES_H #define TRIPLES_H #include <bits/stdc++.h> #include <random> #include <time.h> #define fi first #define se second #define ii pair<int,int> using namespace std; //long long count_triples(std::vector<int> H){ // int n = H.size(); // vector <vector<int>> z[n]; // for (int i = 0; i < n; i++){ // for (int j = i + 1; j < n; j++){ // for (int k = j + 1; k < n; k++){ // int d1 = j - i, d2 = k - i, d3 = k - j; // vector <int> tmp = {d1,d3,d2}; // z[i].push_back(tmp); // // cout << d1 << " " << d2 << " " << d3 << "\n"; // } // } // } // dist(i,j) + dist(j,k) = dist(i,k) // -> d1 + d3 = d2 // for (d1) -> for (d3): // a[i], a[i + d1], a[i + d1 + d3] = d1 , d3, d1 + d3 // // xet a[i] // j = i + a[i] -> co a[j] // TH1: k = j + a[j] -> co a[k] | ok // TH2: k = i + a[j] -> co a[k] | ok // // xet a[i] // k = i + a[i] // TH1: i + a[k] // TH2: k - a[k] // //// xet a[i] //// TH1: //// k - j = a[i] //// j - i = a[j] //// k - i = a[k] //// //// TH2: //// k - j = a[i] //// k = a[i] + j //// j - i = a[k] //// k - i = a[j] // for (int i = 0; i < n; i++) sort(z[i].begin(), z[i].end()); // for (int i = 0; i < n; i++){ // for (auto x : z[i]){ // cout << i << " -> "; // for (auto t : x) cout << t << " "; // cout << "\n"; // } // cout << "\n"; // } // return 10; //} int n; map <array<int,3>, bool> mps; map <pair<int,int>, bool> rock; void ct3(int i, int j, int k){ //cout << " -> " << i << " " << j << " " << k << "\n"; assert(i < j && j < k && i >=0 && k < n); array<int,3> f = {i,j,k}; // if (mps[f] == true){ // for (auto x : gg) cout << x << " "; // cout << "\n"; // } // assert(mps[f] == false); mps[f] = true; } long long count_triples(std::vector<int> H){ n = H.size(); mps.clear(); rock.clear(); int qut = 0; vector <int> f[2 * n]; for (int i = 0; i < n; i++){ f[i + H[i]].push_back(i); // rock[{i + H[i], i}] = 1; } for (int j = 1; j < n - 1; j++){ if (true){ int i = j - H[j]; if (i >= 0){ int k = j + H[i]; if (i >= 0 && k < n && H[k] == k - i) ct3(i,j,k); } } if (true){ int i = j - H[j]; if (i >= 0){ int k = i + H[i]; if (i >= 0 && k < n && j < k && H[k] == k - j) ct3(i,j,k); } } if (true){ int k = j + H[j]; if (k < n){ int i = j - H[k]; if (i >= 0 && k < n && H[i] == k - i) ct3(i,j,k); } } if (true){ int k = j + H[j]; if (k < n){ int i = k - H[k]; if (i >= 0 && k < n && i < j && H[i] == j - i) ct3(i,j,k); } } int pick = j + H[j]; int p = upper_bound(f[pick].begin(), f[pick].end(), j) - f[pick].begin(); for (int ik = p; ik < f[pick].size(); ik++){ int k = f[pick][ik]; assert(k > j); // H[k - H[j]] + H[k] == H[j] if (k - H[j] >= 0 && k - H[j] < j && H[k - H[j]] == k - j){ ct3(k - H[j], j, k); } } // for (int k = j + 1; k < n; k++){ // int i = k - H[j]; // if (i >= j) break; // if (i >= 0 && i < j && ((H[i] == j - i && H[k] == k - j) || (H[i] == k - j && H[k] == j - i))) qut++; // } } for (int i = 0; i < n; i++){ int j = i + H[i]; if (j < n){ int k = i + H[j]; if (k < n && j < k && H[k] == k - j) ct3(i,j,k); } } return (int)mps.size() + qut; } vector<int> construct_range(int M, int K){ vector <int> res; for (int i = 1; i < M; i++) res.push_back(M - i); res.push_back(1); return res; }; #endif // TRIPLES_H
#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...