結果

問題 No.5004 Room Assignment
ユーザー phocomphocom
提出日時 2021-12-01 06:24:45
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 148 ms / 5,000 ms
コード長 4,784 bytes
コンパイル時間 1,487 ms
実行使用メモリ 22,284 KB
スコア 140,224,842
平均クエリ数 7630.36
最終ジャッジ日時 2021-12-01 06:25:08
合計ジャッジ時間 21,525 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge16
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#pragma GCC optimize("Ofast")
#define REP(i, N) for (int i = 0; i < (int)N; i++)
#define FOR(i, a, b) for (int i = a; i < (int)b; i++)
#define ALL(x) (x).begin(), (x).end()

using namespace std;
using Pii = pair<int, int>;
constexpr int inf = 1 << 30;

template <class T>
string to_string(T s);
template <class S, class T>
string to_string(pair<S, T> p);
string to_string(char c) { return string(1, c); }
string to_string(string s) { return s; }
string to_string(const char s[]) { return string(s); }

template <class T>
string to_string(T v) {
  if (v.empty()) return "{}";
  string ret = "{";
  for (auto x : v) ret += to_string(x) + ",";
  ret.back() = '}';
  return ret;
}

template <class S, class T>
string to_string(pair<S, T> p) {
  return "{" + to_string(p.first) + ":" + to_string(p.second) + "}";
}
void debug() { cerr << endl; }

template <class Head, class... Tail>
void debug(Head head, Tail... tail) {
  cerr << to_string(head) << " ";
  debug(tail...);
}

template <class T>
bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}

constexpr int T = 3600, R = 4;
int id = 1;

struct Player {
  int idx;
  int t;
  int s;
  int e;
  Player() : e(0) {}
};

struct Room {
  vector<Player> players;
  int mn, mx;
  int t;
  int e;
  Room() {}
  Room(Player player) {
    players.push_back(player);
    mn = mx = player.s;
    e = 0;
    t = player.t;
  }
  int merged_gap(Room &room) { return max(mx, room.mx) - min(mn, room.mn); }
  void merge(Room &room, int t) {
    for (auto &player : players) {
      player.e += (t - player.t) * room.players.size();
    }
    for (auto &player : room.players) {
      player.e += (t - player.t) * players.size();
      chmin(mn, player.s);
      chmax(mx, player.s);
    }
    for (auto &player : room.players) {
      players.push_back(player);
    }
    e = players.size() * (players.size() - 1) / 2 *
        (200 - (mx - mn) * (mx - mn));
    t = inf;
    for (auto player : players) {
      e -= player.e;
      chmin(t, player.t);
    }
    e = max(0, e);
  }
};

int main(int argc, char **argv) {
  int _;
  cin >> _ >> _;
  vector<Room> rooms;
  vector<int> thrs(101, 3);
  vector<double> ns(100, 1.5);
  REP(i, 101) {
    int d = min(i, 100 - i);
    if (d < 10)
      thrs[i] = 5;
    else if (d < 20)
      thrs[i] = 4;
    else
      thrs[i] = 3;
  }
  int E = 0;
  REP(t, T) {
    int N;
    cin >> N;
    ns.push_back(N);
    double ave = 0;
    REP(i, 50) ave += ns[ns.size() - 1 - i] / 50;
    vector<Pii> ans;
    REP(i, N) {
      Player player;
      player.idx = id++;
      player.t = t;
      cin >> player.s;
      rooms.emplace_back(player);
    }

    auto merge = [&]() {
      while (1) {
        int best = inf;
        Pii cand(-1, -1);
        REP(i, rooms.size()) {
          FOR(j, i + 1, rooms.size()) {
            if (rooms[i].players.size() + rooms[j].players.size() <= 4) {
              if (rooms[i].merged_gap(rooms[j]) <=
                  thrs[rooms[i].mn] + (ave < 1.1)) {
                int v =
                    rooms[i].merged_gap(rooms[j]) -
                    max(rooms[i].mx - rooms[i].mn, rooms[j].mx - rooms[j].mn);
                if (v < best) {
                  best = v;
                  cand = {i, j};
                }
              }
            }
          }
        }
        if (best < inf) {
          ans.emplace_back(rooms[cand.first].players[0].idx,
                           rooms[cand.second].players[0].idx);
          rooms[cand.first].merge(rooms[cand.second], t);
          rooms.erase(rooms.begin() + cand.second);
          if (rooms[cand.first].players.size() == 4) {
            E += rooms[cand.first].e;
            if (0 && rooms[cand.first].e < 1000)
              debug(rooms[cand.first].e, rooms[cand.first].mn,
                    rooms[cand.first].mx);
            rooms.erase(rooms.begin() + cand.first);
          }
        } else {
          break;
        }
      }
    };
    merge();
    if (t + 1 == T) {
      REP(i, 101) thrs[i] = 10;
      merge();
    }
    for (int j = rooms.size() - 1; j >= 0; --j) {
      if (rooms[j].t < t - 150) {
        E += rooms[j].e;
        rooms.erase(rooms.begin() + j);
      }
    }
    cout << ans.size() << endl;
    for (auto p : ans) cout << p.first << " " << p.second << endl;
  }
  for (auto &room : rooms) E += room.e;
  debug(E);
  return 0;
}
0