結果

問題 No.5018 Let's Make a Best-seller Book
ユーザー nikajnikaj
提出日時 2023-10-01 15:41:42
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 49 ms / 400 ms
コード長 9,104 bytes
コンパイル時間 1,496 ms
コンパイル使用メモリ 152,416 KB
実行使用メモリ 24,420 KB
スコア 65,596
平均クエリ数 52.00
最終ジャッジ日時 2023-10-01 15:41:54
合計ジャッジ時間 11,213 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 49 ms
23,844 KB
testcase_01 AC 46 ms
23,820 KB
testcase_02 AC 46 ms
23,412 KB
testcase_03 AC 44 ms
23,424 KB
testcase_04 AC 45 ms
23,640 KB
testcase_05 AC 45 ms
24,060 KB
testcase_06 AC 45 ms
23,424 KB
testcase_07 AC 45 ms
24,024 KB
testcase_08 AC 45 ms
23,832 KB
testcase_09 AC 46 ms
24,420 KB
testcase_10 AC 45 ms
23,520 KB
testcase_11 AC 45 ms
23,532 KB
testcase_12 AC 46 ms
24,384 KB
testcase_13 AC 45 ms
24,336 KB
testcase_14 AC 45 ms
24,036 KB
testcase_15 AC 47 ms
24,012 KB
testcase_16 AC 45 ms
24,060 KB
testcase_17 AC 45 ms
23,244 KB
testcase_18 AC 46 ms
24,024 KB
testcase_19 AC 45 ms
23,640 KB
testcase_20 AC 45 ms
23,640 KB
testcase_21 AC 45 ms
23,412 KB
testcase_22 AC 46 ms
24,036 KB
testcase_23 AC 45 ms
23,412 KB
testcase_24 AC 45 ms
24,024 KB
testcase_25 AC 45 ms
23,412 KB
testcase_26 AC 45 ms
23,400 KB
testcase_27 AC 44 ms
23,664 KB
testcase_28 AC 44 ms
23,640 KB
testcase_29 AC 44 ms
23,664 KB
testcase_30 AC 47 ms
23,388 KB
testcase_31 AC 44 ms
24,060 KB
testcase_32 AC 45 ms
23,532 KB
testcase_33 AC 45 ms
24,396 KB
testcase_34 AC 45 ms
23,652 KB
testcase_35 AC 46 ms
23,676 KB
testcase_36 AC 47 ms
23,676 KB
testcase_37 AC 47 ms
23,412 KB
testcase_38 AC 45 ms
23,820 KB
testcase_39 AC 46 ms
23,676 KB
testcase_40 AC 45 ms
23,664 KB
testcase_41 AC 46 ms
23,844 KB
testcase_42 AC 46 ms
23,832 KB
testcase_43 AC 45 ms
24,288 KB
testcase_44 AC 45 ms
23,640 KB
testcase_45 AC 46 ms
24,036 KB
testcase_46 AC 45 ms
23,664 KB
testcase_47 AC 45 ms
24,336 KB
testcase_48 AC 46 ms
24,396 KB
testcase_49 AC 45 ms
24,120 KB
testcase_50 AC 45 ms
23,412 KB
testcase_51 AC 45 ms
23,424 KB
testcase_52 AC 46 ms
23,412 KB
testcase_53 AC 45 ms
23,532 KB
testcase_54 AC 46 ms
24,336 KB
testcase_55 AC 45 ms
23,640 KB
testcase_56 AC 45 ms
24,036 KB
testcase_57 AC 45 ms
24,336 KB
testcase_58 AC 46 ms
24,264 KB
testcase_59 AC 45 ms
23,640 KB
testcase_60 AC 44 ms
23,424 KB
testcase_61 AC 45 ms
23,652 KB
testcase_62 AC 45 ms
24,360 KB
testcase_63 AC 45 ms
24,396 KB
testcase_64 AC 46 ms
24,264 KB
testcase_65 AC 45 ms
24,276 KB
testcase_66 AC 45 ms
23,424 KB
testcase_67 AC 44 ms
24,384 KB
testcase_68 AC 44 ms
23,652 KB
testcase_69 AC 45 ms
23,712 KB
testcase_70 AC 45 ms
24,036 KB
testcase_71 AC 46 ms
23,652 KB
testcase_72 AC 45 ms
24,012 KB
testcase_73 AC 45 ms
23,688 KB
testcase_74 AC 46 ms
23,376 KB
testcase_75 AC 46 ms
23,844 KB
testcase_76 AC 45 ms
23,820 KB
testcase_77 AC 45 ms
23,532 KB
testcase_78 AC 45 ms
24,336 KB
testcase_79 AC 45 ms
24,060 KB
testcase_80 AC 46 ms
24,024 KB
testcase_81 AC 46 ms
23,532 KB
testcase_82 AC 45 ms
23,820 KB
testcase_83 AC 46 ms
23,532 KB
testcase_84 AC 45 ms
23,388 KB
testcase_85 AC 44 ms
23,676 KB
testcase_86 AC 46 ms
23,664 KB
testcase_87 AC 45 ms
23,892 KB
testcase_88 AC 48 ms
23,832 KB
testcase_89 AC 45 ms
23,376 KB
testcase_90 AC 46 ms
24,264 KB
testcase_91 AC 45 ms
23,832 KB
testcase_92 AC 45 ms
23,412 KB
testcase_93 AC 46 ms
23,376 KB
testcase_94 AC 45 ms
23,652 KB
testcase_95 AC 47 ms
24,360 KB
testcase_96 AC 46 ms
23,652 KB
testcase_97 AC 45 ms
24,024 KB
testcase_98 AC 47 ms
24,036 KB
testcase_99 AC 46 ms
23,664 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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 = min(ep + x, 60);
            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) {
            cerr << turn << " " << money << endl;
            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;
}
0