結果
| 問題 | No.3320 yiwiwiy |
| コンテスト | |
| ユーザー |
 みうね
|
| 提出日時 | 2026-07-09 18:12:31 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.90.0) |
| 結果 |
AC
|
| 実行時間 | 1,124 ms / 2,000 ms |
| コード長 | 9,185 bytes |
| 記録 | |
| コンパイル時間 | 2,364 ms |
| コンパイル使用メモリ | 350,944 KB |
| 実行使用メモリ | 11,528 KB |
| 最終ジャッジ日時 | 2026-07-09 18:13:12 |
| 合計ジャッジ時間 | 40,576 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 73 |
ソースコード
// GPT-5.5 High
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using i128 = __int128_t;
static ll floor_div_i128(i128 a, i128 b) {
// b > 0
if (a >= 0) return (ll)(a / b);
return (ll)(-((-a + b - 1) / b));
}
static ll clamp_ll(ll x, ll l, ll r) {
if (x < l) return l;
if (x > r) return r;
return x;
}
struct Best {
i128 val = -1;
int type = 0;
// type:
// 0: no-block
// 1: all block
// 2: right run
// 3: left run
// 4: two runs
ll k = 0, l = 0, p = 0;
};
struct CaseSolver {
ll I, W, B;
i128 alpha;
Best best;
i128 c(ll a) const {
return (i128)a * (I - a);
}
i128 sum1(ll n) const {
if (n <= 0) return 0;
return (i128)n * (n + 1) / 2;
}
i128 sum2(ll n) const {
if (n <= 0) return 0;
return (i128)n * (n + 1) * (2 * (i128)n + 1) / 6;
}
// sum_{a=l}^{r} a(I-a)
i128 sum_c(ll l, ll r) const {
if (l > r) return 0;
return (i128)I * (sum1(r) - sum1(l - 1))
- (sum2(r) - sum2(l - 1));
}
void update(i128 val, int type, ll k, ll l, ll p) {
if (val > best.val) {
best.val = val;
best.type = type;
best.k = k;
best.l = l;
best.p = p;
}
}
void add_around(vector<ll>& v, i128 num, i128 den, ll lo, ll hi) const {
if (lo > hi) return;
ll q = floor_div_i128(num, den);
for (ll d = -6; d <= 6; d++) {
ll x = q + d;
if (lo <= x && x <= hi) v.push_back(x);
}
v.push_back(lo);
v.push_back(hi);
}
void uniq(vector<ll>& v) const {
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
}
ll best_p_inside(ll l, ll r) const {
// p in [l+1, r-1] maximizing c(p)
ll lo = l + 1;
ll hi = r - 1;
ll p1 = clamp_ll(I / 2, lo, hi);
ll p2 = clamp_ll((I + 1) / 2, lo, hi);
return (c(p2) > c(p1) ? p2 : p1);
}
Best solve() {
best = Best();
ll internal = max(0LL, I - 1);
// Case A:
// No positive block of >=2 w's is used.
// Use as many singleton internal gaps as possible.
{
ll k0 = min(W, internal);
if (k0 == 0) {
update(0, 0, 0, 0, 0);
} else {
ll lo = 1;
ll hi = I - k0;
vector<ll> cand;
// vertex of sum_{a=l}^{l+k0-1} c(a)
// l = (I - (k0 - 1)) / 2
add_around(cand, (i128)I - (k0 - 1), 2, lo, hi);
uniq(cand);
for (ll l : cand) {
i128 R = sum_c(l, l + k0 - 1);
i128 Q = k0 - 1;
update(alpha * R + (i128)B * Q, 0, k0, l, 0);
}
}
}
if (W >= 2) {
// Case B-0:
// all w's in one gap
{
vector<ll> ps = {0, I, I / 2, (I + 1) / 2};
sort(ps.begin(), ps.end());
ps.erase(unique(ps.begin(), ps.end()), ps.end());
for (ll p : ps) {
if (0 <= p && p <= I) {
i128 R = (i128)W * c(p);
update(alpha * R, 1, 0, 0, p);
}
}
}
ll Kmax = min(W - 2, internal);
for (ll k = 1; k <= Kmax; k++) {
ll m = W - k;
// Case B-1:
// block at p, singleton run to the right
{
ll lo = 0;
ll hi = I - 1 - k;
vector<ll> cand;
// vertex of:
// m*c(p) + sum_{a=p+1}^{p+k} c(a)
// p = (W*I - k(k+1)) / (2W)
add_around(
cand,
(i128)W * I - (i128)k * (k + 1),
(i128)2 * W,
lo,
hi
);
uniq(cand);
for (ll p : cand) {
i128 R = (i128)m * c(p) + sum_c(p + 1, p + k);
i128 Q = k - 1;
update(alpha * R + (i128)B * Q, 2, k, 0, p);
}
}
// Case B-2:
// block at p, singleton run to the left
{
ll lo = k + 1;
ll hi = I;
vector<ll> cand;
// vertex:
// p = (W*I + k(k+1)) / (2W)
add_around(
cand,
(i128)W * I + (i128)k * (k + 1),
(i128)2 * W,
lo,
hi
);
uniq(cand);
for (ll p : cand) {
i128 R = (i128)m * c(p) + sum_c(p - k, p - 1);
i128 Q = k - 1;
update(alpha * R + (i128)B * Q, 3, k, 0, p);
}
}
// Case B-3:
// block at p, singleton runs on both sides
if (k >= 2 && k <= I - 2) {
ll lo = 1;
ll hi = I - k - 1;
ll h = m - 1;
vector<ll> cand;
// interval [l, l+k], p is an interior point
// selected singleton gaps are all gaps in the interval except p
// vertex of interval sum only:
// l = (I-k)/2
add_around(cand, (i128)I - k, 2, lo, hi);
// piece where best p is left interior endpoint, j=1
add_around(
cand,
(i128)(k + 1) * (I - k) + (i128)h * (I - 2),
(i128)2 * W,
lo,
hi
);
// piece where best p is right interior endpoint, j=k-1
add_around(
cand,
(i128)(k + 1) * (I - k) + (i128)h * (I - 2 * (k - 1)),
(i128)2 * W,
lo,
hi
);
// boundaries where a global peak enters/leaves the interior
vector<ll> peaks = {I / 2, (I + 1) / 2};
for (ll peak : peaks) {
add_around(cand, (i128)peak - k + 1, 1, lo, hi);
add_around(cand, (i128)peak - 1, 1, lo, hi);
}
uniq(cand);
for (ll l : cand) {
ll r = l + k;
ll p = best_p_inside(l, r);
i128 R = sum_c(l, r) + (i128)(m - 1) * c(p);
i128 Q = k - 2;
update(alpha * R + (i128)B * Q, 4, k, l, p);
}
}
}
}
return best;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
ll Y, I, W, A, B;
cin >> Y >> I >> W >> A >> B;
ll yL = Y / 2;
ll yR = Y - yL;
i128 cy = (i128)yL * yR;
i128 alpha = cy * A;
CaseSolver solver{I, W, B, alpha};
Best best = solver.solve();
vector<ll> x((size_t)I + 1, 0);
if (best.type == 0) {
ll k = best.k;
if (k == 0) {
x[0] = W;
} else {
x[0] = W - k;
for (ll a = best.l; a <= best.l + k - 1; a++) {
x[(size_t)a] = 1;
}
}
} else if (best.type == 1) {
x[(size_t)best.p] = W;
} else if (best.type == 2) {
ll k = best.k;
ll p = best.p;
ll m = W - k;
x[(size_t)p] = m;
for (ll a = p + 1; a <= p + k; a++) {
x[(size_t)a] = 1;
}
} else if (best.type == 3) {
ll k = best.k;
ll p = best.p;
ll m = W - k;
x[(size_t)p] = m;
for (ll a = p - k; a <= p - 1; a++) {
x[(size_t)a] = 1;
}
} else {
ll k = best.k;
ll l = best.l;
ll p = best.p;
ll m = W - k;
ll r = l + k;
x[(size_t)p] = m;
for (ll a = l; a <= r; a++) {
if (a != p) x[(size_t)a] = 1;
}
}
string ans;
ans.reserve((size_t)(Y + I + W));
ans.append((size_t)yL, 'y');
ans.append((size_t)x[0], 'w');
for (ll a = 1; a <= I; a++) {
ans.push_back('i');
ans.append((size_t)x[(size_t)a], 'w');
}
ans.append((size_t)yR, 'y');
cout << ans << '\n';
}
return 0;
}