結果

問題 No.5004 Room Assignment
ユーザー phocom
提出日時 2021-12-01 06:24:45
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.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
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます

ソースコード

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