結果
| 問題 | No.5018 Let's Make a Best-seller Book |
| ユーザー |
 nikaj
|
| 提出日時 | 2023-10-01 15:36:33 |
| 言語 | C++11 (gcc 11.4.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 9,058 bytes |
| コンパイル時間 | 1,469 ms |
| コンパイル使用メモリ | 152,680 KB |
| 実行使用メモリ | 4,380 KB |
| スコア | 0 |
| 最終ジャッジ日時 | 2023-10-01 15:36:38 |
| 合計ジャッジ時間 | 4,868 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
| testcase_56 | -- | - |
| testcase_57 | -- | - |
| testcase_58 | -- | - |
| testcase_59 | -- | - |
| testcase_60 | -- | - |
| testcase_61 | -- | - |
| testcase_62 | -- | - |
| testcase_63 | -- | - |
| testcase_64 | -- | - |
| testcase_65 | -- | - |
| testcase_66 | -- | - |
| testcase_67 | -- | - |
| testcase_68 | -- | - |
| testcase_69 | -- | - |
| testcase_70 | -- | - |
| testcase_71 | -- | - |
| testcase_72 | -- | - |
| testcase_73 | -- | - |
| testcase_74 | -- | - |
| testcase_75 | -- | - |
| testcase_76 | -- | - |
| testcase_77 | -- | - |
| testcase_78 | -- | - |
| testcase_79 | -- | - |
| testcase_80 | -- | - |
| testcase_81 | -- | - |
| testcase_82 | -- | - |
| testcase_83 | -- | - |
| testcase_84 | -- | - |
| testcase_85 | -- | - |
| testcase_86 | -- | - |
| testcase_87 | -- | - |
| testcase_88 | -- | - |
| testcase_89 | -- | - |
| testcase_90 | -- | - |
| testcase_91 | -- | - |
| testcase_92 | -- | - |
| testcase_93 | -- | - |
| testcase_94 | -- | - |
| testcase_95 | -- | - |
| testcase_96 | -- | - |
| testcase_97 | -- | - |
| testcase_98 | -- | - |
| testcase_99 | -- | - |
ソースコード
double TL = 0.01;
int STANDARD = 1;
int DBG = 0;
#include <bits/stdc++.h>
using namespace std;
#define F0(i,n) for (int i=0; i<n; i++)
#define F1(i,n) for (int i=1; i<=n; i++)
#define CL(a,x) memset(x, a, sizeof(x));
#define SZ(x) ((int)x.size())
const int inf = 1000009;
const double pi = acos(-1.0);
typedef pair<int, int> pii;
typedef long long ll;
const double EPS = 1e-9;
const int MOD = 998244353;
#define PR(x) cerr << #x << "=" << x << endl
template<class A, class B>
ostream& operator<<(ostream& os, const pair<A, B>& p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
template<class A, class B, class C>
ostream& operator<<(ostream& os, const tuple<A, B, C>& p) { os << "(" << get<0>(p) << ", " << get<1>(p) << ", " << get<2>(p) << ")"; return os; }
istream& operator>>(istream& is, pii& p) { is>>p.first>>p.second; return is; }
template<class T>
ostream& operator<<(ostream& os, const vector<T>& v) { os << "["; F0(i,SZ(v)) { if (i>0) os << ","; os << v[i]; } os << "]"; return os; }
template<class T>
ostream& operator<<(ostream& os, const set<T>& v) { os << "{"; int f=1; for(auto i:v) { if(f)f=0;else os << ","; cerr << i; } os << "}" << endl; return os; }
template<class T, class R>
ostream& operator<<(ostream& os, const map<T,R>& v) { os << "{"; int f=1; for(auto i:v) { if(f)f=0;else os << ", "; cerr << i.first << ":" << i.second; } os << "}" << endl; return os; }
//#pragma GCC optimize("O3")
#ifndef __APPLE__
inline ll GetTSC() {
ll lo, hi;
asm volatile ("rdtsc": "=a"(lo), "=d"(hi));
return lo + (hi << 32);
}
inline double GetSeconds() {
return GetTSC() / 3.0e9;
}
#else
#include <sys/time.h>
double GetSeconds() {
timeval tv;
gettimeofday(&tv, 0);
return tv.tv_sec + tv.tv_usec * 1e-6;
}
#endif
const int MAX_RAND = 1 << 30;
struct Rand {
ll x, y, z, w, o;
Rand() {}
Rand(ll seed) { reseed(seed); o = 0; }
inline void reseed(ll seed) { x = 0x498b3bc5 ^ seed; y = 0; z = 0; w = 0; F0(i, 20) mix(); }
inline void mix() { ll t = x ^ (x << 11); x = y; y = z; z = w; w = w ^ (w >> 19) ^ t ^ (t >> 8); }
inline ll rand() { mix(); return x & (MAX_RAND - 1); }
inline int nextInt(int n) { return rand() % n; }
inline int nextInt(int L, int R) { return rand()%(R - L + 1) + L; }
inline int nextBool() { if (o < 4) o = rand(); o >>= 2; return o & 1; }
double nextDouble() { return rand() * 1.0 / MAX_RAND; }
};
Rand my(2023);
double saveTime;
double t_o[20];
ll c_o[20];
void Init() {
saveTime = GetSeconds();
F0(i, 20) t_o[i] = 0.0;
F0(i, 20) c_o[i] = 0;
}
double Elapsed() { return GetSeconds() - saveTime; }
void Report() {
double tmp = Elapsed();
cerr << "-------------------------------------" << endl;
cerr << "Elapsed time: " << tmp << " sec" << endl;
double total = 0.0; F0(i, 20) { if (t_o[i] > 0) cerr << "t_o[" << i << "] = " << t_o[i] << endl; total += t_o[i]; } cerr << endl; //if (total > 0) cerr << "Total spent: " << total << endl;
F0(i, 20) if (c_o[i] > 0) cerr << "c_o[" << i << "] = " << c_o[i] << endl;
cerr << "-------------------------------------" << endl;
}
struct AutoTimer {
int x;
double t;
AutoTimer(int x) : x(x) {
t = Elapsed();
}
~AutoTimer() {
t_o[x] += Elapsed() - t;
}
};
#define AT(i) AutoTimer a##i(i)
//#define AT(i)
const int N = 16;
int n, T, x, query_type, turn, sold;
ll money;
int L[N], S[N], P[N], R[N], old_R[N], needp[N];
double D[N], Mult[64][N], coeff[N];
double D1[N], D2[N], DE[N];
string ans;
const int DX[]={-1,0,1,0};
const int DY[]={0,1,0,-1};
const string CS="nesw";
const string HS="URDL";
void Query() {
if (STANDARD) {
cout << query_type;
if (query_type == 1) {
F0(i, n) cout << " " << L[i];
} else {
cout << " " << x;
}
cout << endl;
cin >> money;
F0(i, n) cin >> S[i];
F0(i, n) {
int ep = P[i];
if (query_type == 2) ep += x;
if (R[i] != 0) {
if (S[i] * 10 >= 3 * R[i]) ep = min(ep + 1, 60);
if (S[i] * 10 < R[i]) ep = max(ep - 1, -60);
}
cin >> P[i];
//cerr << endl << i << " " << P[i] << " " << ep << " " << R[i] << " " << S[i] << endl;
assert(P[i] == ep);
}
F0(i, n) {
int er = R[i];
er -= S[i];
cin >> R[i];
assert(R[i] == er);
}
} else {
if (query_type == 1) {
F0(i, n) { money -= L[i] * 500; }
assert(money >= 0);
} else {
assert(1 <= x && x <= 5);
money -= 500000 << (x - 1);
assert(money >= 0);
F0(i, n) { P[i] += x; P[i] = min(P[i], 60); P[i] = max(P[i], -60); }
}
F0(i, n) {
// 0.5, 1.5
// 0.75, 1.25
S[i] = min(R[i], int(pow(R[i], 0.5) * pow(1.05, P[i]) * D[i] * Mult[turn][i]));
if (R[i] != 0) {
if (S[i] * 10 >= 3 * R[i]) P[i] = min(P[i] + 1, 60);
if (S[i] * 10 < 1 * R[i]) P[i] = max(P[i] - 1, -60);
}
sold += S[i];
money += S[i] * 1000;
R[i] -= S[i];
}
}
}
void Solve() {
F0(i, n) {
D1[i] = 0.5;
D2[i] = 1.5;
}
for (turn = 0; turn < T; turn++) {
if (turn == 0) {
query_type = 2; x = 2;
} else if (turn < 40 && money > 1500000) {
PR(turn);
query_type = 2; x = 1;
}
else {
query_type = 1;
int B = 0;
int cnt = 0;
F0(i, n) {
if (P[i] >= -B) cnt++; else D2[i] = D1[i];
L[i] = 0;
double s = 0.17 - turn * 0.001;
DE[i] = pow(D1[i], 0.5 + s) * pow(D2[i], 0.5 - s);
}
if (turn >= 42) {
int m = money / 500;
F0(i, n) L[i] = m / n + (i < (m%n));
F0(its, 1000) {
int i1 = my.nextInt(n);
int i2 = my.nextInt(n);
if (i1 != i2) {
int r = L[i1];
while (my.nextInt(4)) r /= 4;
int y = my.nextInt(r + 1);
double old_c1 = pow(L[i1] + R[i1], 0.5) * pow(1.05, P[i1]) * DE[i1];
double old_c2 = pow(L[i2] + R[i2], 0.5) * pow(1.05, P[i2]) * DE[i2];
double c1 = pow(L[i1] + R[i1] - y, 0.5) * pow(1.05, P[i1]) * DE[i1];
double c2 = pow(L[i2] + R[i2] + y, 0.5) * pow(1.05, P[i2]) * DE[i2];
if (old_c1 + old_c2 < c1 + c2) {
L[i1] -= y;
L[i2] += y;
}
}
}
} else {
F0(i, n) if (P[i] >= -B) {
bool grow = false;
for (int nr = R[i]; nr <= R[i] + 700 && (nr - R[i]) <= money / 500 / cnt; nr++) if (nr > 0) {
double c = pow(nr, 0.5) * pow(1.05, P[i]);
int need = (3 * nr + 9) / 10;
double mult_needs_to_be = need / c;
if (mult_needs_to_be <= DE[i] * 0.74) { L[i] = nr - R[i]; grow = true; }
}
}
}
}
F0(i, n) {
R[i] += L[i];
coeff[i] = pow(R[i], 0.5) * pow(1.05, P[i]);
old_R[i] = R[i];
}
Query();
F0(i, n) if (old_R[i] != 0) {
double at_least = S[i] / coeff[i];
double at_most = (S[i] + 1) / coeff[i];
D1[i] = max(D1[i], at_least / 1.25);
D2[i] = min(D2[i], at_most / 0.75);
}
F0(i, n) cerr << P[i] << " "; cerr << endl;
}
if (!STANDARD) { F0(i, n) {
//assert(D1[i] <= D[i] && D[i] <= D2[i]);
cerr << i << " " << D1[i] << " " << D[i] << " " << D2[i] << endl;
}
}
}
void ReadInput() {
cin >> T >> n >> money;
}
void ReadStuff() {
cin >> T >> n;
money = 2000000;
F0(i, n) cin >> D[i];
F0(turn, T) F0(i, n) cin >> Mult[turn][i];
}
int main(int argc, char* argv[]) {
int seed1 = 0, seed2 = 0;
if(argc>1) {
seed1 = seed2 = atoi(argv[1]);
if (argc > 2) {
DBG = atoi(argv[2]);
}
STANDARD=0;
}
if(STANDARD) {
ReadInput();
Solve();
return 0;
}
for (int seed=seed1; seed<=seed2; seed++) {
if(seed>=1 && seed<=100) {
char inp[128];
sprintf(inp, "in/%04d.txt", seed);
char outp[128];
sprintf(outp, "out/%04d.txt", seed);
ignore = freopen(inp, "r", stdin);
ReadStuff();
//cerr << "Seed #" << seed << " ";
Solve();
cout << "Score = " << sold << endl;
} else {
// Generate
throw;
}
}
return 0;
}