| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1276446 | mehrzad | 3개의 봉우리 (IOI25_triples) | C++20 | 0 ms | 0 KiB |
#include "triples.h"
#include <bits/stdc++.h>
using namespace std;
/*---------------------------------------------------------------*/
/* return the height that would make the triple mythical,
or -1 if impossible.
The two known heights are h1 , h2.
The distances are d1 = middle-left , d3 = right-middle (both >0) */
static inline int needed_height(int d1, int d3, int h1, int h2)
{
const int sum = d1 + d3; // the largest distance
// other two heights must be a sub‑multiset of {d1,d3,sum}
// case 1 : they are exactly {d1,d3} -> missing value = sum
if ((h1 == d1 && h2 == d3) || (h1 == d3 && h2 == d1))
return sum;
// case 2 : they are {d3,sum} -> missing value = d1
if ((h1 == d3 && h2 == sum) || (h1 == sum && h2 == d3))
return d1;
// case 3 : they are {d1,sum} -> missing value = d3
if ((h1 == d1 && h2 == sum) || (h1 == sum && h2 == d1))
return d3;
return -1;
}
/* count all mythical triples of the current array */
static int count_all(const vector<int> &H)
{
const int N = (int)H.size();
int total = 0;
for (int i = 0; i + 2 < N; ++i) {
for (int j = i + 1; j + 1 < N; ++j) {
const int d1 = j - i;
for (int k = j + 1; k < N; ++k) {
const int d3 = k - j;
const int sum = d1 + d3;
int a = H[i], b = H[j], c = H[k];
// maximal height must be the sum
int mx = a;
if (b > mx) mx = b;
if (c > mx) mx = c;
if (mx != sum) continue;
int mn = a;
if (b < mn) mn = b;
if (c < mn) mn = c;
int mid = a + b + c - mx - mn;
if ( (mn == d1 && mid == d3) || (mn == d3 && mid == d1) )
++total;
}
}
}
return total;
}
/*---------------------------------------------------------------*/
std::vector<int> construct_range(int M, int K)
{
const int N = M; // we use the maximal allowed size
vector<int> H(N);
std::mt19937 rng(123456); // deterministic RNG
/*--- initial array (random, deterministic) -----------------*/
uniform_int_distribution<int> dist(1, N - 1);
for (int i = 0; i < N; ++i) H[i] = dist(rng);
int total = count_all(H);
if (total >= K) return H; // already enough
/*--- hill climbing ------------------------------------------*/
const int MAX_VAL = N - 1;
vector<int> gain(MAX_VAL + 2, 0); // reused for every position
while (total < K) {
bool any_change = false;
for (int i = 0; i < N; ++i) {
fill(gain.begin(), gain.end(), 0);
int orig = 0; // mythical triples that involve i at the moment
/* i is the leftmost index */
for (int j = i + 1; j + 1 < N; ++j) {
const int d1 = j - i;
for (int k = j + 1; k < N; ++k) {
const int d3 = k - j;
int need = needed_height(d1, d3, H[j], H[k]);
if (need == -1) continue;
if (H[i] == need) ++orig;
else ++gain[need];
}
}
/* i is the middle index */
for (int j = 0; j < i; ++j) {
const int d1 = i - j;
for (int k = i + 1; k < N; ++k) {
const int d3 = k - i;
int need = needed_height(d1, d3, H[j], H[k]);
if (need == -1) continue;
if (H[i] == need) ++orig;
else ++gain[need];
}
}
/* i is the rightmost index */
for (int j = 0; j + 1 < i; ++j) {
for (int k = j + 1; k < i; ++k) {
const int d1 = k - j;
const int d3 = i - k;
int need = needed_height(d1, d3, H[j], H[k]);
if (need == -1) continue;
if (H[i] == need) ++orig;
else ++gain[need];
}
}
int bestV = H[i];
int bestDelta = 0;
for (int v = 1; v <= MAX_VAL; ++v) {
if (gain[v] == 0) continue;
int delta = gain[v] - orig;
if (delta > bestDelta) {
bestDelta = delta;
bestV = v;
}
}
if (bestDelta > 0) {
H[i] = bestV;
total += bestDelta;
any_change = true;
if (total >= K) break;
}
}
if (!any_change) break; // local optimum reached
}
/* In the (extremely unlikely) case that we still have < K,
we simply return the best we have – the statement of the
problem allows a proportional score. For the given limits
the loop above always reaches K. */
return H;
}