結果

問題 No.5004 Room Assignment
ユーザー takumi152takumi152
提出日時 2021-12-01 01:31:03
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 164 ms / 5,000 ms
コード長 6,897 bytes
コンパイル時間 3,296 ms
実行使用メモリ 22,368 KB
スコア 138,923,997
平均クエリ数 7626.28
最終ジャッジ日時 2021-12-01 01:31:28
合計ジャッジ時間 24,901 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 141 ms
21,948 KB
testcase_01 AC 140 ms
22,032 KB
testcase_02 AC 140 ms
21,900 KB
testcase_03 AC 140 ms
21,936 KB
testcase_04 AC 150 ms
22,152 KB
testcase_05 AC 147 ms
21,924 KB
testcase_06 AC 140 ms
21,608 KB
testcase_07 AC 141 ms
21,924 KB
testcase_08 AC 139 ms
22,164 KB
testcase_09 AC 141 ms
21,864 KB
testcase_10 AC 139 ms
22,116 KB
testcase_11 AC 140 ms
21,896 KB
testcase_12 AC 144 ms
21,804 KB
testcase_13 AC 163 ms
22,212 KB
testcase_14 AC 139 ms
22,344 KB
testcase_15 AC 142 ms
21,936 KB
testcase_16 AC 140 ms
22,224 KB
testcase_17 AC 143 ms
21,912 KB
testcase_18 AC 139 ms
22,128 KB
testcase_19 AC 141 ms
22,128 KB
testcase_20 AC 141 ms
21,900 KB
testcase_21 AC 141 ms
21,972 KB
testcase_22 AC 141 ms
21,900 KB
testcase_23 AC 164 ms
21,924 KB
testcase_24 AC 140 ms
22,032 KB
testcase_25 AC 139 ms
22,140 KB
testcase_26 AC 142 ms
21,948 KB
testcase_27 AC 143 ms
21,804 KB
testcase_28 AC 139 ms
21,912 KB
testcase_29 AC 140 ms
22,104 KB
testcase_30 AC 139 ms
22,176 KB
testcase_31 AC 140 ms
21,948 KB
testcase_32 AC 142 ms
22,224 KB
testcase_33 AC 143 ms
21,828 KB
testcase_34 AC 151 ms
21,936 KB
testcase_35 AC 142 ms
22,356 KB
testcase_36 AC 141 ms
21,780 KB
testcase_37 AC 139 ms
22,104 KB
testcase_38 AC 139 ms
21,912 KB
testcase_39 AC 140 ms
21,936 KB
testcase_40 AC 140 ms
21,912 KB
testcase_41 AC 139 ms
21,804 KB
testcase_42 AC 146 ms
21,924 KB
testcase_43 AC 143 ms
21,900 KB
testcase_44 AC 139 ms
21,780 KB
testcase_45 AC 141 ms
21,936 KB
testcase_46 AC 140 ms
21,936 KB
testcase_47 AC 141 ms
22,104 KB
testcase_48 AC 140 ms
21,900 KB
testcase_49 AC 141 ms
22,368 KB
testcase_50 AC 142 ms
21,972 KB
testcase_51 AC 149 ms
21,792 KB
testcase_52 AC 141 ms
21,924 KB
testcase_53 AC 141 ms
21,792 KB
testcase_54 AC 141 ms
22,044 KB
testcase_55 AC 141 ms
21,792 KB
testcase_56 AC 142 ms
22,128 KB
testcase_57 AC 140 ms
21,792 KB
testcase_58 AC 140 ms
21,792 KB
testcase_59 AC 143 ms
21,900 KB
testcase_60 AC 140 ms
21,984 KB
testcase_61 AC 141 ms
21,912 KB
testcase_62 AC 139 ms
22,140 KB
testcase_63 AC 140 ms
21,972 KB
testcase_64 AC 139 ms
21,960 KB
testcase_65 AC 138 ms
21,792 KB
testcase_66 AC 141 ms
21,948 KB
testcase_67 AC 143 ms
21,924 KB
testcase_68 AC 151 ms
21,924 KB
testcase_69 AC 138 ms
22,080 KB
testcase_70 AC 141 ms
22,116 KB
testcase_71 AC 141 ms
21,776 KB
testcase_72 AC 141 ms
21,912 KB
testcase_73 AC 141 ms
21,948 KB
testcase_74 AC 140 ms
21,900 KB
testcase_75 AC 143 ms
21,924 KB
testcase_76 AC 140 ms
21,924 KB
testcase_77 AC 141 ms
21,900 KB
testcase_78 AC 143 ms
21,960 KB
testcase_79 AC 141 ms
22,020 KB
testcase_80 AC 141 ms
22,212 KB
testcase_81 AC 139 ms
21,960 KB
testcase_82 AC 141 ms
21,780 KB
testcase_83 AC 142 ms
22,152 KB
testcase_84 AC 144 ms
22,164 KB
testcase_85 AC 147 ms
22,164 KB
testcase_86 AC 142 ms
21,948 KB
testcase_87 AC 142 ms
21,792 KB
testcase_88 AC 141 ms
22,044 KB
testcase_89 AC 141 ms
22,032 KB
testcase_90 AC 140 ms
22,224 KB
testcase_91 AC 140 ms
21,924 KB
testcase_92 AC 142 ms
21,768 KB
testcase_93 AC 143 ms
21,888 KB
testcase_94 AC 140 ms
21,936 KB
testcase_95 AC 138 ms
21,924 KB
testcase_96 AC 139 ms
21,948 KB
testcase_97 AC 140 ms
21,912 KB
testcase_98 AC 138 ms
21,924 KB
testcase_99 AC 140 ms
21,768 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx2")

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <queue>
#include <stack>
#include <array>
#include <unordered_set>
#include <random>
#include <cmath>
#include <cassert>

#include <x86intrin.h>

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() {
    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)
    #endif
  }
};

using namespace std;

typedef long long int ll;
typedef pair<int, int> Pii;

const ll mod = 1000000007;

timer theTimer;
xorshift64 theRandom;
mt19937 theMersenne(1);

// constants
constexpr int turn_limit = 3600;
constexpr int r = 4;

constexpr int n_total = 5400;

constexpr array<int, 5> score_mult = {0, 0, 1, 3, 6};
constexpr int base_score = 200;

// structs
struct room_info {
  int room_host;
  int min_skill;
  int max_skill;
  vector<int> turn_joined;

  room_info(int host_id, int host_skill, int create_turn) {
    this->room_host = host_id;
    this->min_skill = host_skill;
    this->max_skill = host_skill;
    this->turn_joined = vector<int>({create_turn});
  }

  void join(int member_skill, int join_turn) {
    assert((int) this->turn_joined.size() < 4);
    assert(this->turn_joined[this->turn_joined.size()-1] <= join_turn);

    this->min_skill = min(this->min_skill, member_skill);
    this->max_skill = max(this->max_skill, member_skill);
    this->turn_joined.push_back(join_turn);
  }

  int calc_raw_score() {
    int score = (base_score - (max_skill - min_skill) * (max_skill - min_skill)) * score_mult[this->turn_joined.size()];
    for (int i = 0; i < (int) this->turn_joined.size() - 1; i++) {
      for (int j = i + 1; j < (int) this->turn_joined.size(); j++) {
        score -= this->turn_joined[j] - this->turn_joined[i];
      }
    }
    return score;
  }

  int calc_score() {
    int score = calc_raw_score();
    return max(0, score);
  }

  int simulate_score(int member_skill, int join_turn) {
    assert((int) this->turn_joined.size() < 4);
    assert(this->turn_joined[this->turn_joined.size()-1] <= join_turn);

    int temp_min_skill = min(this->min_skill, member_skill);
    int temp_max_skill = max(this->max_skill, member_skill);

    int score = (base_score - (temp_max_skill - temp_min_skill) * (temp_max_skill - temp_min_skill)) * score_mult[this->turn_joined.size() + 1];
    for (int i = 0; i < (int) this->turn_joined.size() - 1; i++) {
      for (int j = i + 1; j < (int) this->turn_joined.size(); j++) {
        score -= this->turn_joined[j] - this->turn_joined[i];
      }
    }
    for (int i = 0; i < (int) this->turn_joined.size(); i++) {
      score -= join_turn - this->turn_joined[i];
    }
    return score;
  }
};

// internals
int turn_count = 0;
vector<vector<room_info> > room_list(5);

vector<int> get_input() {
  int n;
  cin >> n;
  vector<int> added_player(n);
  for (auto &x: added_player) cin >> x;
  return added_player;
}

void output(vector<Pii> op) {
  cout << op.size() << endl;
  for (auto &x: op) cout << x.first << " " << x.second << endl;
}

void solve() {
  auto calc_total_score = [&]() {
    int total_score = 0;
    for (int i = 2; i <= 4; i++) {
      for (auto &room: room_list[i]) total_score += room.calc_score();
    }
    return total_score;
  };

  int current_player_id = 1;
  while (turn_count < turn_limit) {
    auto input = get_input();

    vector<Pii> op;
    for (auto &skill: input) {
      int best_room_score_delta = -1;
      int best_room_idx_i = -1;
      int best_room_idx_j = -1;
      for (int i = 1; i <= 3; i++) {
        for (int j = 0; j < (int) room_list[i].size(); j++) {
          if (max(room_list[i][j].max_skill, skill) - min(room_list[i][j].min_skill, skill) <= 3) {
            int room_score_delta = room_list[i][j].simulate_score(skill, turn_count) - room_list[i][j].calc_score();
            if (room_score_delta > best_room_score_delta) {
              best_room_score_delta = room_score_delta;
              best_room_idx_i = i;
              best_room_idx_j = j;
            }
          }
        }
      }
      if (best_room_idx_i != -1 && best_room_idx_j != -1) {
        op.emplace_back(room_list[best_room_idx_i][best_room_idx_j].room_host, current_player_id);
        room_list[best_room_idx_i][best_room_idx_j].join(skill, turn_count);
        room_list[best_room_idx_i+1].push_back(room_list[best_room_idx_i][best_room_idx_j]);
        swap(room_list[best_room_idx_i][best_room_idx_j], room_list[best_room_idx_i][room_list[best_room_idx_i].size()-1]);
        room_list[best_room_idx_i].pop_back();
      }
      else {
        room_list[1].push_back(room_info(current_player_id, skill, turn_count));
      }
      current_player_id++;
    }

    #ifdef DEBUG
    cerr << "turn_count = " << setw(4) << turn_count << ", score = " << setw(7) << calc_total_score() << endl;
    #endif

    output(op);
    turn_count++;
  }

  cerr << "score = " << calc_total_score() << endl;
}

int main(int argc, char *argv[]) {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int _t, _r;
  cin >> _t >> _r;

  solve();

  return 0;
}
0