結果
問題 |
No.3306 Life is Easy?
|
ユーザー |
|
提出日時 | 2025-10-05 15:55:10 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 11,651 bytes |
コンパイル時間 | 3,230 ms |
コンパイル使用メモリ | 366,948 KB |
実行使用メモリ | 7,844 KB |
最終ジャッジ日時 | 2025-10-05 15:56:05 |
合計ジャッジ時間 | 55,186 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | WA * 25 RE * 10 |
ソースコード
#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> #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; 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 day_num, stone_num; vector<vector<ll>> stone_day_price; // outputs ll ans; // environment // state vector<pair<int, bool>> action_of_day; // stone_id, is_buy vector<vector<pair<int, bool>>> actions_for_stone; // day_idx, is_buy // score vector<ll> stone_score; ll total_score; void get_first_input() { cin >> day_num >> stone_num; stone_day_price = vector<vector<ll>>(day_num, vector<ll>(stone_num)); for (int i = 0; i < day_num; i++) { for (int j = 0; j < stone_num; j++) { cin >> stone_day_price[i][j]; } } } void init() { action_of_day = vector<pair<int, bool>>(day_num, make_pair(0, false)); actions_for_stone = vector<vector<pair<int, bool>>>(day_num, vector<pair<int, bool>>()); for (int i = 0; i < day_num; i++) { actions_for_stone[0].emplace_back(i, false); } stone_score = vector<ll>(stone_num); total_score = 0; } void update_score_partial(int stone_idx) { total_score -= stone_score[stone_idx]; stone_score[stone_idx] = 0; priority_queue<int, vector<int>, greater<int>> que; for (auto &[day, is_buy]: actions_for_stone[stone_idx]) { if (is_buy) { que.emplace(stone_day_price[day][stone_idx]); } else if (!que.empty()) { auto buy_price = que.top(); que.pop(); stone_score[stone_idx] += stone_day_price[day][stone_idx] - buy_price; } } total_score += stone_score[stone_idx]; } void update_score_full() { stone_score.assign(stone_num, 0); total_score = 0; for (int i = 0; i < stone_num; i++) { update_score_partial(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 = 1e9; 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 < 0.50) { int d = theRandom.nextUIntMod(day_num); bool b = theRandom.nextUIntMod(2) == 0; int s = theRandom.nextUIntMod(stone_num); auto act = action_of_day[d]; action_of_day[d] = make_pair(s, b); actions_for_stone[act.first].erase(find(actions_for_stone[act.first].begin(), actions_for_stone[act.first].end(), make_pair(d, act.second))); actions_for_stone[s].insert(lower_bound(actions_for_stone[s].begin(), actions_for_stone[s].end(), make_pair(d, b)), make_pair(d, b)); update_score_partial(act.first); update_score_partial(s); 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) { // cerr << "Y " << iter_count << " " << d << " " << (int) b << " " << s << endl; last_score = score; if (score > best_score) { best_score = score; } } else if (theRandom.nextDouble() < exp(double(score - last_score) / temperature)) { // accept // cerr << "Y " << iter_count << " " << d << " " << (int) b << " " << s << endl; last_score = score; } else { // rollback // cerr << "N " << iter_count << " " << d << " " << (int) b << " " << s << endl; // for (int i = 0; i < day_num; i++) { // cerr << "A " << i << " " << action_of_day[i].first << " " << (int) action_of_day[i].second << endl; // } // for (int i = 0; i < stone_num; i++) { // cerr << "S " << i << " " << stone_score[i] << " "; // for (auto &x: actions_for_stone[i]) { // cerr << "(" << x.first << ", " << (int) x.second << ") "; // } // cerr << endl; // } action_of_day[d] = act; actions_for_stone[s].erase(find(actions_for_stone[s].begin(), actions_for_stone[s].end(), make_pair(d, b))); actions_for_stone[act.first].insert(lower_bound(actions_for_stone[act.first].begin(), actions_for_stone[act.first].end(), make_pair(d, act.second)), make_pair(d, act.second)); update_score_partial(act.first); update_score_partial(s); // cerr << score << " " << last_score << " " << get_score() << endl; } } else if (roll < 1.00) { int d1 = theRandom.nextUIntMod(day_num); int d2 = theRandom.nextUIntMod(day_num); int s = theRandom.nextUIntMod(stone_num); if (d1 == d2) continue; if (d1 > d2) swap(d1, d2); auto act1 = action_of_day[d1]; action_of_day[d1] = make_pair(s, true); actions_for_stone[act1.first].erase(find(actions_for_stone[act1.first].begin(), actions_for_stone[act1.first].end(), make_pair(d1, act1.second))); actions_for_stone[s].insert(lower_bound(actions_for_stone[s].begin(), actions_for_stone[s].end(), make_pair(d1, true)), make_pair(d1, true)); auto act2 = action_of_day[d2]; action_of_day[d2] = make_pair(s, false); actions_for_stone[act2.first].erase(find(actions_for_stone[act2.first].begin(), actions_for_stone[act2.first].end(), make_pair(d2, act2.second))); actions_for_stone[s].insert(lower_bound(actions_for_stone[s].begin(), actions_for_stone[s].end(), make_pair(d2, false)), make_pair(d2, false)); update_score_partial(act1.first); update_score_partial(act2.first); update_score_partial(s); 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 action_of_day[d1] = act1; actions_for_stone[s].erase(find(actions_for_stone[s].begin(), actions_for_stone[s].end(), make_pair(d1, true))); actions_for_stone[act1.first].insert(lower_bound(actions_for_stone[act1.first].begin(), actions_for_stone[act1.first].end(), make_pair(d1, act1.second)), make_pair(d1, act1.second)); action_of_day[d2] = act2; actions_for_stone[s].erase(find(actions_for_stone[s].begin(), actions_for_stone[s].end(), make_pair(d2, false))); actions_for_stone[act2.first].insert(lower_bound(actions_for_stone[act2.first].begin(), actions_for_stone[act2.first].end(), make_pair(d2, act2.second)), make_pair(d2, act2.second)); update_score_partial(act1.first); update_score_partial(act2.first); update_score_partial(s); } } // auto ss = stone_score; // update_score_full(); // if (last_score != get_score()) { // cerr << "X " << last_score << " " << get_score() << endl; // for (int i = 0; i < day_num; i++) { // cerr << "A " << i << " " << action_of_day[i].first << " " << (int) action_of_day[i].second << endl; // } // for (int i = 0; i < stone_num; i++) { // cerr << "S " << i << " " << ss[i] << " " << stone_score[i] << " "; // for (auto &x: actions_for_stone[i]) { // cerr << "(" << x.first << ", " << (int) x.second << ") "; // } // cerr << endl; // } // assert(false); // } // 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; }