結果
問題 |
No.3302 Sense Battle
|
ユーザー |
|
提出日時 | 2025-10-05 17:14:05 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,902 ms / 2,000 ms |
コード長 | 6,692 bytes |
コンパイル時間 | 2,638 ms |
コンパイル使用メモリ | 336,336 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-10-05 17:14:45 |
合計ジャッジ時間 | 39,882 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 18 |
ソースコード
#ifdef __GNUC__ #pragma GCC optimize ("O3") #pragma GCC optimize ("unroll-loops") // #pragma GCC target ("avx2") #endif #include <iostream> #include <fstream> #include <iomanip> #include <vector> #include <array> #include <algorithm> #include <utility> #include <string> #include <queue> #include <stack> #include <set> #include <unordered_set> #include <unordered_map> #include <bitset> #include <random> #include <functional> #include <cmath> #include <cassert> #include <atcoder/fenwicktree> #ifdef _MSC_VER #include <intrin.h> #else #include <x86intrin.h> #endif struct xorshift64 { unsigned long long int x = 88172645463325252ULL; inline unsigned short nextUShort() { x = x ^ (x << 7); return x = x ^ (x >> 9); } inline unsigned int nextUShortMod(unsigned long long int mod) { x = x ^ (x << 7); x = x ^ (x >> 9); return ((x & 0x0000ffffffffffff) * mod) >> 48; } inline unsigned int nextUInt() { x = x ^ (x << 7); return x = x ^ (x >> 9); } inline unsigned int nextUIntMod(unsigned long long int mod) { x = x ^ (x << 7); x = x ^ (x >> 9); return ((x & 0x00000000ffffffff) * mod) >> 32; } inline unsigned long long int nextULL() { x = x ^ (x << 7); return x = x ^ (x >> 9); } inline double nextDouble() { x = x ^ (x << 7); x = x ^ (x >> 9); return (double)x * 5.42101086242752217e-20; } }; struct timer { double t = 0.0; double lastStop = 0.0; bool stopped = false; timer() { restart(); } inline void restart() { t = now(); stopped = false; } inline void start() { if (stopped) { t += now() - lastStop; stopped = false; } } inline void stop() { if (!stopped) { lastStop = now(); stopped = true; } } inline double time() { if (stopped) return lastStop - t; else return now() - t; } inline double now() { #ifdef _MSC_VER #ifdef LOCAL return __rdtsc() * 2.857142857142857e-10; // 1 / 3.5e9, for local (Ryzen 9 3950X) #else //return __rdtsc() * 3.5714285714285715e-10; // 1 / 2.8e9, for AWS EC2 C3 (Xeon E5-2680 v2) //return __rdtsc() * 3.4482758620689656e-10; // 1 / 2.9e9, for AWS EC2 C4 (Xeon E5-2666 v3) //return __rdtsc() * 3.333333333333333e-10; // 1 / 3.0e9, for AWS EC2 C5 (Xeon Platinum 8124M / Xeon Platinum 8275CL) return __rdtsc() * 4.3478260869565215e-10; // 1 / 2.3e9, for yukicoder judge #endif #else unsigned long long l, h; __asm__ ("rdtsc" : "=a"(l), "=d"(h)); #ifdef LOCAL return (double)(l | h << 32) * 2.857142857142857e-10; // 1 / 3.5e9, for local (Ryzen 9 3950X) #else //return (double)(l | h << 32) * 3.5714285714285715e-10; // 1 / 2.8e9, for AWS EC2 C3 (Xeon E5-2680 v2) //return (double)(l | h << 32) * 3.4482758620689656e-10; // 1 / 2.9e9, for AWS EC2 C4 (Xeon E5-2666 v3) //return (double)(l | h << 32) * 3.333333333333333e-10; // 1 / 3.0e9, for AWS EC2 C5 (Xeon Platinum 8124M / Xeon Platinum 8275CL) return (double)(l | h << 32) * 4.3478260869565215e-10; // 1 / 2.3e9, for yukicoder judge #endif #endif } }; using namespace std; using namespace atcoder; typedef long long int ll; typedef unsigned long long int ull; typedef pair<int, int> Pii; typedef unsigned char uchar; const ll mod = 1000000007; timer theTimer; xorshift64 theRandom; mt19937 theMersenne(1); // hyper parameters // structs // enums // constants // inputs int turn_num; vector<ll> a, b; // outputs ll ans; // environment // state fenwick_tree<ll> is_attack; // 0 -> a, 1 -> b fenwick_tree<ll> attack_gain; // score ll total_score; void get_first_input() { cin >> turn_num; a = vector<ll>(turn_num); b = vector<ll>(turn_num); for (int i = 0; i < turn_num; i++) { cin >> a[i] >> b[i]; } } void init() { is_attack = fenwick_tree<ll>(turn_num); attack_gain = fenwick_tree<ll>(turn_num); for (int i = 0; i < turn_num; i++) { attack_gain.add(i, a[i]); } } void update_score_partial(int turn_idx) { if (is_attack.sum(turn_idx, turn_idx + 1) == 0) { // a -> b attack_gain.add(turn_idx, -a[turn_idx]); is_attack.add(turn_idx, 1); total_score += b[turn_idx] + attack_gain.sum(0, turn_idx); total_score -= a[turn_idx] * is_attack.sum(turn_idx + 1, turn_num); } else { // b -> a attack_gain.add(turn_idx, a[turn_idx]); is_attack.add(turn_idx, -1); total_score -= b[turn_idx] + attack_gain.sum(0, turn_idx); total_score += a[turn_idx] * is_attack.sum(turn_idx + 1, turn_num); } } void update_score_full() { total_score = 0; ll total_attack_gain = 0; for (int i = 0; i < turn_num; i++) { if (is_attack.sum(i, i + 1) == 0) { total_attack_gain += a[i]; } else { total_score += total_attack_gain + b[i]; } } } ll get_score() { return total_score; } void solve() { update_score_full(); ll score = get_score(); ll last_score = score; ll best_score = score; const double base_temperature = 1e15; const double target_temperature = 1e-2; // const double decay_rate = 4e-5; double temperature = base_temperature; int iter_count = 0; double time_start = theTimer.time(); const double time_limit = 1.900; while (theTimer.time() < time_limit) { double roll = theRandom.nextDouble(); if (roll < 1.00) { int t = theRandom.nextUIntMod(turn_num); update_score_partial(t); score = get_score(); #ifdef DEBUG if (iter_count % 100000 == 0) cerr << iter_count << " " << score << " " << last_score << " " << best_score << " " << temperature << " " << theTimer.time() << endl; #endif if (score >= last_score) { last_score = score; if (score > best_score) { best_score = score; } } else if (theRandom.nextDouble() < exp(double(score - last_score) / temperature)) { // accept last_score = score; } else { // rollback update_score_partial(t); } } // temperature *= 1.0 - decay_rate; temperature = exp(log(base_temperature) - ((log(base_temperature) - log(target_temperature)) * ((theTimer.time() - time_start) * (1.0 / (time_limit - time_start))))); iter_count++; } cerr << "iter_count = " << iter_count << endl; cerr << "score = " << score << endl; cerr << "best_score = " << best_score << endl; cerr << "temperature = " << temperature << endl; ans = best_score; } void output_ans() { cout << ans << endl; } int main(int argc, char *argv[]) { cin.tie(0); ios::sync_with_stdio(false); get_first_input(); init(); solve(); output_ans(); return 0; }