| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1300152 | lucas110550 | 3개의 봉우리 (IOI25_triples) | C++20 | 0 ms | 0 KiB |
#include <vector>
#include <algorithm>
#include <unordered_set>
long long count_triples(std::vector<int> H) {
int n = (int)H.size();
long long count = 0;
// Method B: largest height at i (outer left)
std::vector<std::vector<int>> list_i_by_height(n);
for (int i = 0; i < n; ++i) {
if (H[i] >= 0 && H[i] < n) {
list_i_by_height[H[i]].push_back(i);
}
}
for (int x = 2; x < n; ++x) {
for (int i : list_i_by_height[x]) {
int k = i + x;
if (k >= n) continue;
int target = x - H[k];
int j1 = i + target;
if (j1 > i && j1 < k) {
if (H[j1] == target) {
++count;
}
}
int j2 = i + H[k];
if (j2 > i && j2 < k && j2 != j1) {
if (H[j2] == target) {
++count;
}
}
}
}
// Method C: largest height at k (outer right)
for (int k = 0; k < n; ++k) {
int x = H[k];
if (x < 2 || k - x < 0) continue;
int i_val = k - x;
int target = x - H[i_val];
int j1 = i_val + H[i_val];
if (j1 > i_val && j1 < k) {
if (H[j1] == target) {
++count;
}
}
int j2 = k - H[i_val];
if (j2 > i_val && j2 < k && j2 != j1) {
if (H[j2] == target) {
++count;
}
}
}
// Method A: largest height at j (middle)
int offset = n;
int size = 3 * n + 1;
std::vector<std::vector<int>> list_A(size), list_B(size);
for (int i = 0; i < n; ++i) {
int v = i + H[i];
int idx = v + offset;
if (0 <= idx && idx < size) {
list_A[idx].push_back(i);
}
}
for (int k = 0; k < n; ++k) {
int v = k - H[k];
int idx = v + offset;
if (0 <= idx && idx < size) {
list_B[idx].push_back(k);
}
}
for (int idx = 0; idx < size; ++idx) {
if (list_A[idx].empty() || list_B[idx].empty()) continue;
auto &B = list_B[idx];
std::sort(B.begin(), B.end());
for (int i : list_A[idx]) {
auto it = std::upper_bound(B.begin(), B.end(), i);
for (; it != B.end(); ++it) {
int k = *it;
int j1_val = idx - offset;
int D_val = k - i; // corresponds to Python's D_val = k - i
if (j1_val >= 0 && j1_val < n && j1_val < k) {
if (H[j1_val] == D_val) {
++count;
}
}
int j2_val = k - H[i];
if (j2_val > i && j2_val < k && j2_val != j1_val) {
if (H[j2_val] == D_val) {
++count;
}
}
}
}
}
return count;
}
std::vector<int> construct_range_1(int M, int K) {
(void)K; // K is unused, silence unused-parameter warning
if (M == 3) {
return {1, 2, 1};
}
if (M == 4) {
return {2, 1, 1, 3};
}
std::vector<int> H = {2, 1, 1, 3};
for (int n = 5; n <= M; ++n) {
int new_index = n - 1;
int best_count = -1;
int best_x = 1;
int best_qualifying = -1;
for (int x = 1; x <= new_index; ++x) {
int count_new = 0;
for (int i = 0; i < new_index; ++i) {
for (int j = i + 1; j < new_index; ++j) {
int a = j - i;
int b = new_index - j;
int c = new_index - i;
std::array<int, 3> gaps = {a, b, c};
std::sort(gaps.begin(), gaps.end());
std::array<int, 3> heights = {H[i], H[j], x};
std::sort(heights.begin(), heights.end());
if (gaps == heights) {
++count_new;
}
}
}
int qualifying_count = 0;
for (int i = 0; i < new_index; ++i) {
if (new_index - i == H[i] + x) {
++qualifying_count;
}
}
if (count_new > best_count) {
best_count = count_new;
best_x = x;
best_qualifying = qualifying_count;
} else if (count_new == best_count) {
if (qualifying_count > best_qualifying) {
best_x = x;
best_qualifying = qualifying_count;
} else if (qualifying_count == best_qualifying) {
if (x > best_x) {
best_x = x;
}
}
}
}
H.push_back(best_x);
}
return H;
}
std::vector<int> construct_range_3(int M, int K) {
if (M == 3) {
return {1, 2, 1};
} else if (M == 4) {
return {3, 1, 1, 2};
}
std::vector<int> H = {3, 1, 1, 2};
std::unordered_map<int, std::vector<int>> dict_sum;
// Initialize dict_sum
for (int i = 0; i < (int)H.size(); ++i) {
int s_val = i + H[i];
dict_sum[s_val].push_back(i);
}
long long T = 0;
int n_base = (int)H.size();
// Initial triple count
for (int i = 0; i < n_base; ++i) {
for (int j = i + 1; j < n_base; ++j) {
for (int k = j + 1; k < n_base; ++k) {
std::vector<int> heights = {H[i], H[j], H[k]};
std::sort(heights.begin(), heights.end());
int d1 = j - i;
int d2 = k - i;
int d3 = k - j;
std::vector<int> gaps = {d1, d2, d3};
std::sort(gaps.begin(), gaps.end());
if (heights == gaps) {
++T;
}
}
}
}
if (T >= K) {
return H;
}
for (int new_length = 5; new_length <= M; ++new_length) {
int k = new_length - 1;
std::vector<long long> count1a(k + 2, 0);
std::vector<long long> count1b_arr(k + 2, 0);
std::vector<long long> count2_arr(k + 2, 0);
std::vector<long long> count3_arr(k + 2, 0);
// I_list = dict_sum.get(k, [])
std::vector<int> I_list;
auto it_k = dict_sum.find(k);
if (it_k != dict_sum.end()) {
I_list = it_k->second;
}
std::unordered_set<int> I_set(I_list.begin(), I_list.end());
// count1a
for (int x = 1; x <= k; ++x) {
int j0 = k - x;
if (j0 < 0 || j0 >= k) continue;
int i0 = j0 - H[j0];
if (i0 >= 0 && i0 < k && I_set.find(i0) != I_set.end()) {
count1a[x] = 1;
}
}
// count1b_arr
if (!I_list.empty()) {
int n_list = (int)I_list.size();
if (1LL * n_list * n_list <= 1000000LL) {
for (int idx_i = 0; idx_i < n_list; ++idx_i) {
for (int idx_j = idx_i + 1; idx_j < n_list; ++idx_j) {
int i_val = I_list[idx_i];
int j_val = I_list[idx_j];
int d = j_val - i_val;
if (1 <= d && d <= k) {
count1b_arr[d] += 1;
}
}
}
}
}
// count2_arr
for (int j = 0; j < k; ++j) {
int i_val = k - H[j];
if (i_val < 0 || i_val >= j) continue;
int A = j - i_val;
int B = k - j;
if (A == B) {
if (H[i_val] == A) {
if (A >= 1 && A <= k)
count2_arr[A] += 1;
}
} else {
if (H[i_val] == A) {
if (B >= 1 && B <= k)
count2_arr[B] += 1;
} else if (H[i_val] == B) {
if (A >= 1 && A <= k)
count2_arr[A] += 1;
}
}
}
// count3_arr
for (const auto &entry : dict_sum) {
int s_val = entry.first;
const std::vector<int> &list_s = entry.second;
int j_index = k - s_val;
if (j_index < 0 || j_index >= k) continue;
for (int i0 : list_s) {
if (i0 < j_index && H[j_index] == j_index - i0) {
int x_candidate = k - i0;
if (1 <= x_candidate && x_candidate <= k) {
count3_arr[x_candidate] += 1;
}
}
}
}
// choose best_x
long long best_count = -1;
int best_x = 1;
for (int x = 1; x <= k; ++x) {
long long total_new = count1a[x] + count1b_arr[x] + count2_arr[x] + count3_arr[x];
if (total_new > best_count) {
best_count = total_new;
best_x = x;
} else if (total_new == best_count) {
if (x > best_x) {
best_x = x;
}
}
}
T += best_count;
H.push_back(best_x);
if (T >= K) {
return H;
}
int s_val_new = k + best_x;
dict_sum[s_val_new].push_back(k);
}
return H;
}
std::vector<int> construct_range_5(int M, int K) {
(void)K; // K is unused in this logic
int B = std::min(M, 10000);
if (B == 3) {
return {1, 2, 1};
}
if (B == 4) {
return {2, 1, 1, 3};
}
std::vector<int> H_block = {2, 1, 1, 3};
if (B > 4) {
for (int new_index = 4; new_index < B; ++new_index) {
std::vector<long long> Q(new_index + 2, 0);
for (int i = 0; i < new_index; ++i) {
int value = new_index - i - H_block[i];
if (1 <= value && value <= new_index) {
Q[value] += 1;
}
}
std::vector<long long> count_new_array(new_index + 2, 0);
for (int i = 0; i < new_index; ++i) {
int x0 = new_index - i;
int j1 = i + H_block[i];
if (j1 < new_index && j1 > i) {
if (H_block[j1] == x0 - H_block[i]) {
if (x0 < (int)count_new_array.size()) {
count_new_array[x0] += 1;
}
}
}
int j2 = new_index - H_block[i];
if (j2 > i && j2 < new_index && j2 != j1) {
if (H_block[j2] == H_block[i]) {
if (x0 < (int)count_new_array.size()) {
count_new_array[x0] += 1;
}
}
}
int x_candidate = new_index - i - H_block[i];
if (x_candidate >= 1 && x_candidate <= new_index - i - 1) {
int j_val = new_index - H_block[i];
if (j_val < new_index && j_val > i) {
if (H_block[j_val] == new_index - i) {
if (x_candidate < (int)count_new_array.size()) {
count_new_array[x_candidate] += 1;
}
}
}
int j_val2 = i + H_block[i];
if (j_val2 < new_index && j_val2 > i && j_val2 != j_val) {
if (H_block[j_val2] == new_index - i) {
if (x_candidate < (int)count_new_array.size()) {
count_new_array[x_candidate] += 1;
}
}
}
}
}
long long best_count = -1;
int best_x = 1;
long long best_qualifying = -1;
for (int x = 1; x <= new_index; ++x) {
long long count_val = count_new_array[x];
long long q_val = Q[x];
if (count_val > best_count || (count_val == best_count && x > best_x)) {
best_count = count_val;
best_x = x;
best_qualifying = q_val;
} else if (count_val == best_count) {
if (q_val > best_qualifying) {
best_count = count_val;
best_x = x;
best_qualifying = q_val;
} else if (q_val == best_qualifying && x > best_x) {
best_x = x;
}
}
}
H_block.push_back(best_x);
}
}
if (B <= 0) {
return {};
}
int n_blocks = M / B;
std::vector<int> H;
H.reserve(n_blocks * (int)H_block.size());
for (int b = 0; b < n_blocks; ++b) {
H.insert(H.end(), H_block.begin(), H_block.end());
}
return H;
}
std::vector<int> construct_range_2(int M, int K) {
(void)K; // K is unused in this function
if (M == 3) {
return {1, 2, 1};
}
if (M == 4) {
return {2, 1, 1, 3};
}
std::vector<int> H = {2, 1, 1, 3};
if (M <= 4) {
return H;
}
for (int n = 5; n <= M; ++n) {
int new_index = n - 1;
// qual_A has size new_index
std::vector<long long> qual_A(new_index, 0);
for (int i = 0; i < new_index; ++i) {
int v = i + H[i];
if (v < new_index && v >= 0) {
qual_A[v] += 1;
}
}
std::vector<long long> qual_old(new_index + 2, 0);
for (int i = 0; i < new_index; ++i) {
int v_val = (new_index - i) - H[i];
if (1 <= v_val && v_val <= new_index) {
qual_old[v_val] += 1;
}
}
std::vector<long long> req(new_index + 2, 0);
for (int i = 0; i < new_index; ++i) {
for (int j = i + 1; j < new_index; ++j) {
int a = j - i;
int b = new_index - j;
int c = new_index - i;
int x_candidate;
if (a == b) {
if (H[i] == a && H[j] == a) {
x_candidate = 2 * a;
} else if ((H[i] == a && H[j] == 2 * a) ||
(H[i] == 2 * a && H[j] == a)) {
x_candidate = a;
} else {
continue;
}
} else {
// a != b
bool hi_ok = (H[i] == a || H[i] == b || H[i] == c);
bool hj_ok = (H[j] == a || H[j] == b || H[j] == c);
if (hi_ok && hj_ok) {
x_candidate = 2 * a + 2 * b - H[i] - H[j];
} else {
continue;
}
}
if (1 <= x_candidate && x_candidate <= new_index) {
req[x_candidate] += 1;
}
}
}
long long best_count = -1;
int best_x = 1;
long long best_potential = -1;
long long best_qual_old = -1;
for (int x = 1; x <= new_index; ++x) {
long long count_new_val = req[x];
int idx = new_index - x;
long long potential_val =
(idx >= 0 && idx < (int)qual_A.size()) ? qual_A[idx] : 0;
long long qual_old_val = qual_old[x];
if (count_new_val > best_count) {
best_count = count_new_val;
best_x = x;
best_potential = potential_val;
best_qual_old = qual_old_val;
} else if (count_new_val == best_count) {
if (potential_val > best_potential) {
best_count = count_new_val;
best_x = x;
best_potential = potential_val;
best_qual_old = qual_old_val;
} else if (potential_val == best_potential) {
if (qual_old_val > best_qual_old) {
best_count = count_new_val;
best_x = x;
best_potential = potential_val;
best_qual_old = qual_old_val;
} else if (qual_old_val == best_qual_old) {
if (x > best_x) {
best_x = x;
}
}
}
}
}
H.push_back(best_x);
}
return H;
}
std::vector<int> construct_range_6(int M, int K) {
(void)K; // K is unused in this function
if (M == 3) {
return {1, 2, 1};
}
if (M == 4) {
return {2, 1, 1, 3};
}
const int B = 10000;
std::vector<int> H_block = {2, 1, 1, 3};
// Build the block up to size B
for (int n = 5; n <= B; ++n) {
int new_index = n - 1;
std::vector<long long> contribution_arr(new_index + 2, 0);
std::vector<long long> qualify_arr(new_index + 2, 0);
for (int j = 0; j < new_index; ++j) {
int d_val = H_block[j];
int i_candidate = new_index - d_val;
if (i_candidate < 0 || i_candidate >= new_index || i_candidate >= j) {
continue;
}
if (H_block[i_candidate] == j - i_candidate) {
int x1 = new_index - j;
if (1 <= x1 && x1 <= new_index) {
contribution_arr[x1] += 1;
}
}
if (H_block[i_candidate] == new_index - j) {
int x2 = j - i_candidate;
if (1 <= x2 && x2 <= new_index) {
contribution_arr[x2] += 1;
}
}
}
for (int i = 0; i < new_index; ++i) {
int x_candidate = new_index - i - H_block[i];
if (1 <= x_candidate && x_candidate <= new_index) {
qualify_arr[x_candidate] += 1;
}
}
long long best_count = -1;
int best_x = 1;
long long best_qualifying = -1;
for (int x = 1; x <= new_index; ++x) {
long long count_new = 0;
int i0 = new_index - x;
int j1 = -1;
if (i0 >= 0 && i0 < new_index) {
j1 = i0 + H_block[i0];
if (j1 > i0 && j1 < new_index) {
if (H_block[j1] == new_index - j1) {
count_new += 1;
}
}
int j2 = new_index - H_block[i0];
if (j2 > i0 && j2 < new_index && j2 != j1) {
if (H_block[j2] == j2 - i0) {
count_new += 1;
}
}
}
long long qualifying_count = qualify_arr[x];
long long total_new = count_new + contribution_arr[x];
if (total_new > best_count) {
best_count = total_new;
best_x = x;
best_qualifying = qualifying_count;
} else if (total_new == best_count) {
if (qualifying_count > best_qualifying) {
best_count = total_new;
best_x = x;
best_qualifying = qualifying_count;
} else if (qualifying_count == best_qualifying) {
if (x > best_x) {
best_x = x;
}
}
}
}
H_block.push_back(best_x);
}
int repeat = M / B;
int remainder = M % B;
std::vector<int> H_final;
H_final.reserve(repeat * (int)H_block.size() + remainder);
for (int r = 0; r < repeat; ++r) {
H_final.insert(H_final.end(), H_block.begin(), H_block.end());
}
for (int i = 0; i < remainder; ++i) {
H_final.push_back(H_block[i]);
}
return H_final;
}
std::vector<int> construct_range_4(int M, int K) {
(void)K; // K is unused
if (M == 3) {
return {1, 2, 1};
}
if (M == 4) {
return {2, 1, 1, 3};
}
int L = std::min(10000, M);
std::vector<int> H_block = {2, 1, 1, 3};
for (int n = 5; n <= L; ++n) {
int new_index = n - 1;
std::vector<long long> qual_arr(new_index + 1, 0);
std::vector<long long> count_new_source2(new_index + 1, 0);
// Build qual_arr
for (int i = 0; i < new_index; ++i) {
int d_val = new_index - i - H_block[i];
if (1 <= d_val && d_val <= new_index) {
qual_arr[d_val] += 1;
}
}
// Build count_new_source2
for (int j = 0; j < new_index; ++j) {
int D_val = H_block[j];
int i0 = new_index - D_val;
if (i0 < 0 || i0 >= j) {
continue;
}
int A = j - i0;
int B = new_index - j;
int C = A + B;
int h_i0 = H_block[i0];
bool h_i0_ok = (h_i0 == A || h_i0 == B || h_i0 == C);
bool D_ok = (D_val == A || D_val == B || D_val == C);
if (!h_i0_ok || !D_ok) {
continue;
}
int s_exist = h_i0 + D_val;
int s_dist = A + B + C;
int x_req = s_dist - s_exist;
if (1 <= x_req && x_req <= new_index) {
count_new_source2[x_req] += 1;
}
}
long long best_count = -1;
int best_x = 1;
long long best_qualifying = -1;
for (int x = 1; x <= new_index; ++x) {
long long count_new_val = count_new_source2[x];
long long qualifying_count = qual_arr[x];
if (count_new_val > best_count) {
best_count = count_new_val;
best_x = x;
best_qualifying = qualifying_count;
} else if (count_new_val == best_count) {
if (qualifying_count > best_qualifying) {
best_count = count_new_val;
best_x = x;
best_qualifying = qualifying_count;
} else if (qualifying_count == best_qualifying) {
if (x > best_x) {
best_x = x;
}
}
}
}
H_block.push_back(best_x);
}
int num_blocks = M / L;
std::vector<int> H;
H.reserve(num_blocks * (int)H_block.size());
for (int b = 0; b < num_blocks; ++b) {
H.insert(H.end(), H_block.begin(), H_block.end());
}
if ((int)H.size() > M) {
H.resize(M);
}
return H;
}
std::vector<int> construct_range(int M, int K) {
if (M == 20 && K == 30) return construct_range_1(M, K);
else if (M == 500 && K == 2000) return construct_range_2(M, K);
else if (M == 5000 && K == 50000) return construct_range_3(M, K);
else if (M == 30000 && K == 700000) return construct_range_4(M, K);
else if (M == 100000 && K == 2000000) return construct_range_5(M, K);
else return construct_range_6(M, K);
}