結果
| 問題 |
No.3320 yiwiwiy
|
| コンテスト | |
| ユーザー |
 のらら
|
| 提出日時 | 2025-10-07 18:21:05 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,123 bytes |
| コンパイル時間 | 3,272 ms |
| コンパイル使用メモリ | 181,800 KB |
| 実行使用メモリ | 67,380 KB |
| 最終ジャッジ日時 | 2025-10-31 18:56:06 |
| 合計ジャッジ時間 | 42,571 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | WA * 30 TLE * 1 -- * 42 |
ソースコード
#include <iostream>
#include <algorithm>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
//#define endl "\n";
ll Q, Y, I, W;
ll A, B;
void printYIW(){
for(int i = 0; i < Y; i++) cout << "y";
for(int i = 0; i < I; i++) cout << "i";
for(int i = 0; i < W; i++) cout << "w";
cout << endl;
}
void printIWIWI(){
ll cntiw = min(I - 1, W);
ll restI = I - cntiw;
ll restW = W - cntiw;
for(int i = 0; i < Y; i++) cout << "y";
for(int i = 0; i < cntiw; i++) cout << "iw";
for(int i = 0; i < I; i++) cout << "i";
for(int i = 0; i < W; i++) cout << "w";
cout << endl;
}
void printYIWIY(){
for(int i = 0; i < Y / 2; i++) cout << "y";
for(int i = 0; i < I / 2; i++) cout << "i";
for(int i = 0; i < W; i++) cout << "w";
for(int i = 0; i < I - I / 2; i++) cout << "i";
for(int i = 0; i < Y - Y / 2; i++) cout << "y";
cout << endl;
}
void printX(ll numMaxIwiwiL, ll numMaxIwiwiR, ll leftI, ll rightI){
for(int i = 0; i < Y / 2; i++) cout << "y";
for(int i = 0; i < leftI - numMaxIwiwiL; i++) cout << "i";
for(int i = 0; i < numMaxIwiwiL; i++) cout << "wi";
for(int i = 0; i < W - numMaxIwiwiL - numMaxIwiwiR; i++) cout << "w";
for(int i = 0; i < numMaxIwiwiR; i++) cout << "iw";
for(int i = 0; i < rightI - numMaxIwiwiR; i++) cout << "i";
for(int i = 0; i < Y - Y / 2; i++) cout << "y";
cout << endl;
}
string chk = "iwi";
int main(){
cin >> Q;
for(int q = 1; q <= Q; q++){
cin >> Y >> I >> W >> A >> B;
bool isOK_yiwiy = false, isOK_iwiwi = false;
if(Y >= 2 && I >= 2 && W >= 1) isOK_yiwiy = true;
if(I >= 3 && W >= 2) isOK_iwiwi = true;
if(isOK_yiwiy){
if(isOK_iwiwi){
//両方作れる
//基本yyyyyyiiiiiiwwwwwiiiiiiyyyyyがよい
//左右それぞれiwiwiにする
//iが多い方に端数を持たせるのがよい？
ll leftI = I / 2, rightI = I - I / 2;
auto make_str = [&](ll x, ll y)->string{
string retS = "";
for(int i = 0; i < leftI - x; i++) retS += "i";
for(int i = 0; i < x; i++) retS += "wi";
for(int i = 0; i < W - x - y; i++) retS += "w";
for(int i = 0; i < y; i++) retS += "iw";
for(int i = 0; i < rightI - y; i++) retS += "i";
return retS;
};
auto make_str2 = [&](ll x, ll y, ll z)->string{
string retS = "";
for(int i = 0; i < x; i++) retS += "i";
for(int i = 0; i < z - 1; i++) retS += "wi";
retS += "w";
for(int i = 0; i < y; i++) retS += "i";
return retS;
};
auto calcnum = [&](string s)->__int128{
vector<vector<ll>> dp(I + W + 1, vector<ll>(4, 0));
dp[0][0] = 1;
for(int i = 0; i < I + W; i++){
for(int k = 0; k <= 3; k++){
dp[i + 1][k] += dp[i][k];
if(k < 3 && s[i] == chk[k]){
dp[i + 1][k + 1] += dp[i][k];
}
}
}
return dp[I + W][3];
};
auto f = [&](ll x, ll y)->__int128{
string s = make_str(x, y);
return calcnum(s);
};
auto calcval = [&](__int128 num, ll x, ll y)->__int128{
ll cntB = (x > 0 ? x - 1: 0) + (y > 0 ? y - 1: 0);
return num * (__int128)(Y / 2) * (Y - Y / 2) * A + (__int128)cntB * B;
};
__int128 ret1 = calcval(f(0, 0), 0, 0);
__int128 numMaxIwiwiL = 0, numMaxIwiwiR = 0;
for(ll i = 2; i <= 5; i++){
if(min(W - 1, rightI - 1) >= i){
__int128 tmp = calcval(f(0, i), 0, i);
if(tmp > ret1){
ret1 = tmp;
numMaxIwiwiL = 0;
numMaxIwiwiR = i;
}
}
}
//iwiwiを三分探索する
ll rest = min((W - 1) / 2, (leftI - 1 + rightI - 1) / 2);
if(rest >= 2){
ll l = 2, r = rest;
while(r - l > 2){
ll m1 = (l * 2 + r) / 3;
ll m2 = (l + r * 2) / 3;
if(calcval(f(m1, m1),m1,m1) < calcval(f(m2, m2),m2,m2)) l = m1;
else r = m2;
}
__int128 tmpMax = calcval(f(l, l),l,l);
ll chk = l;
for(int i = l + 1; i <= r; i++){
__int128 tmp = calcval(f(i, i),i,i);
if(tmpMax < tmp){
tmpMax = tmp;
chk = i;
}
}
//周辺を調べる
for(int i = 0; i <= 5; i++){
if(chk + i > min(W - chk - 1, rightI - 1)) break;
__int128 tmp = calcval(f(chk, chk+i),chk,chk+i);
if(tmp > ret1){
ret1 = tmp;
numMaxIwiwiL = chk;
numMaxIwiwiR = chk + i;
}
}
}
//iかwを全部iwiwiにする
ll usedW = min(W, I - 1);
ll left = 1 + (I - (usedW + 1)) / 2;
ll right = 1 + (I - (usedW + 1)) - (I - (usedW + 1)) / 2;
string s = make_str2(left, right, usedW);
__int128 tmp = calcval(calcnum(s),0,0) + (W - 1) * B;
if(ret1 < tmp){
for(int i = 0; i < Y / 2; i++) cout << "y";
cout << s;
for(int i = 0; i < W - usedW; i++) cout << "w";
for(int i = 0; i < Y - Y / 2; i++) cout << "y";
cout << endl;
continue;
}
//頑張る
printX(numMaxIwiwiL, numMaxIwiwiR, leftI, rightI);
continue;
}else{
//yiwiyだけ作れる
//yyyyyyiiiiiiwwwwwiiiiiiyyyyyyみたいなのがよい
//左右のyiはできるだけ同じ数がよい
printYIWIY();
continue;
}
}else{
if(isOK_iwiwi){
//iwiwiだけ作れる(貪欲に作る)
printIWIWI();
continue;
}else{
//0なのでそのまま並べて出力
printYIW();
continue;
}
}
}
return 0;
}