結果
| 問題 | No.2713 Just Solitaire |
| ユーザー |
 takumi152
|
| 提出日時 | 2024-03-31 16:39:52 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,496 bytes |
| コンパイル時間 | 3,864 ms |
| コンパイル使用メモリ | 266,404 KB |
| 実行使用メモリ | 6,824 KB |
| 最終ジャッジ日時 | 2024-09-30 21:06:49 |
| 合計ジャッジ時間 | 43,182 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1,903 ms
6,816 KB |
| testcase_01 | AC | 1,901 ms
6,820 KB |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | RE | - |
| testcase_05 | RE | - |
| testcase_06 | WA | - |
| testcase_07 | RE | - |
| testcase_08 | WA | - |
| testcase_09 | RE | - |
| testcase_10 | RE | - |
| testcase_11 | RE | - |
| testcase_12 | RE | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | RE | - |
| testcase_16 | WA | - |
| testcase_17 | RE | - |
| testcase_18 | RE | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | RE | - |
| testcase_22 | RE | - |
| testcase_23 | RE | - |
| testcase_24 | RE | - |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | WA | - |
| testcase_28 | RE | - |
| testcase_29 | RE | - |
| 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
vector<vector<int>> card_bonus_index;
// state
vector<bool> use_card;
// score
vector<int> bonus_missing_card_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() {
card_bonus_index = vector<vector<int>>(card_num);
for (int i = 0; i < bonus_num; i++) {
for (auto &c: bonus_cards[i]) {
card_bonus_index[c].push_back(i);
}
}
use_card = vector<bool>(card_num, true);
}
void update_score_partial(int card_idx, bool is_after_update) {
if (!use_card[card_idx]) return;
for (auto &b: card_bonus_index[card_idx]) {
if (is_after_update) {
bonus_missing_card_count[b]--;
if (bonus_missing_card_count[b] == 0) total_bonus_value += bonus_values[b];
}
else {
bonus_missing_card_count[b]++;
if (bonus_missing_card_count[b] == 1) total_bonus_value -= bonus_values[b];
}
}
total_card_cost += card_costs[card_idx] * (is_after_update ? 1 : -1);
}
void update_score_full() {
bonus_missing_card_count = vector<int>(bonus_num);
for (int i = 0; i < bonus_num; i++) {
bonus_missing_card_count[i] = bonus_cards[i].size();
}
total_card_cost = 0;
total_bonus_value = 0;
for (int i = 0; i < card_num; i++) {
update_score_partial(i, true);
}
for (auto &x: bonus_missing_card_count) cerr << x << " ";
cerr << endl;
}
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(card_num);
update_score_partial(i, false);
use_card[i] = !use_card[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);
use_card[i] = !use_card[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);
if (i1 == i2) continue;
update_score_partial(i1, false);
update_score_partial(i2, false);
use_card[i1] = !use_card[i1];
use_card[i2] = !use_card[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);
use_card[i1] = !use_card[i1];
use_card[i2] = !use_card[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;
}