結果

問題 No.2713 Just Solitaire
ユーザー takumi152takumi152
提出日時 2024-03-31 16:39:52
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 8,496 bytes
コンパイル時間 4,328 ms
コンパイル使用メモリ 267,564 KB
実行使用メモリ 6,676 KB
最終ジャッジ日時 2024-03-31 16:40:36
合計ジャッジ時間 43,548 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,902 ms
6,676 KB
testcase_01 AC 1,902 ms
6,676 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 -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0