結果
問題 | No.2713 Just Solitaire |
ユーザー | takumi152 |
提出日時 | 2024-03-31 15:55:47 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 8,583 bytes |
コンパイル時間 | 3,550 ms |
コンパイル使用メモリ | 265,744 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-09-30 20:58:10 |
合計ジャッジ時間 | 71,107 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,902 ms
6,820 KB |
testcase_01 | AC | 1,903 ms
6,820 KB |
testcase_02 | WA | - |
testcase_03 | AC | 1,902 ms
6,820 KB |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | AC | 1,903 ms
6,820 KB |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | WA | - |
testcase_29 | WA | - |
testcase_30 | WA | - |
testcase_31 | WA | - |
testcase_32 | WA | - |
testcase_33 | WA | - |
ソースコード
#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 card_num, bonus_num; vector<ll> card_costs; vector<ll> bonus_values; vector<vector<int>> bonus_cards; // outputs ll ans; // environment // state vector<bool> take_bonus; // score vector<int> card_use_count; ll total_card_cost; ll total_bonus_value; void get_first_input() { cin >> card_num >> bonus_num; card_costs.resize(card_num); for (auto &x: card_costs) cin >> x; bonus_values.resize(bonus_num); for (auto &x: bonus_values) cin >> x; bonus_cards.resize(bonus_num); for (auto &x: bonus_cards) { int k; cin >> k; x.resize(k); for (auto &y: x) { cin >> y; y--; } } } void init() { take_bonus = vector<bool>(bonus_num); } void update_score_partial(int bonus_idx, bool is_after_update) { if (!take_bonus[bonus_idx]) return; for (auto &c: bonus_cards[bonus_idx]) { if (is_after_update) { card_use_count[c]++; if (card_use_count[c] == 1) total_card_cost += card_costs[c]; } else { card_use_count[c]--; if (card_use_count[c] == 0) total_card_cost -= card_costs[c]; } } total_bonus_value += bonus_values[bonus_idx] * (is_after_update ? 1 : -1); } void update_score_full() { card_use_count = vector<int>(card_num, 0); total_card_cost = 0; total_bonus_value = 0; for (int i = 0; i < bonus_num; i++) { update_score_partial(i, true); } } ll get_score() { return total_bonus_value - total_card_cost; } void solve() { update_score_full(); int score = get_score(); int last_score = score; int best_score = score; const double base_temperature = 1e12; 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 i = theRandom.nextUIntMod(bonus_num); update_score_partial(i, false); take_bonus[i] = !take_bonus[i]; update_score_partial(i, true); 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(i, false); take_bonus[i] = !take_bonus[i]; update_score_partial(i, true); score = last_score; } } else if (roll < 1.00) { int i1 = theRandom.nextUIntMod(bonus_num); int i2 = theRandom.nextUIntMod(bonus_num); update_score_partial(i1, false); update_score_partial(i2, false); take_bonus[i1] = !take_bonus[i1]; take_bonus[i2] = !take_bonus[i2]; update_score_partial(i1, true); update_score_partial(i2, true); 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(i1, false); update_score_partial(i2, false); take_bonus[i1] = !take_bonus[i1]; take_bonus[i2] = !take_bonus[i2]; update_score_partial(i1, true); update_score_partial(i2, true); score = last_score; } } // 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; }