#983738 (C++17) No.2680 研究室配属

• 問題: No.2680 研究室配属
• ユーザー: kekenx
• 提出日時: 2024-05-26 23:17:51
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: TLE
• 実行時間: -
• コード長: 1,075 bytes
• コンパイル時間: 1,598 ms
• コンパイル使用メモリ: 107,568 KB
• 実行使用メモリ: 13,056 KB
• 最終ジャッジ日時: 2024-05-26 23:18:00
• 合計ジャッジ時間: 8,719 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 10,624 KB
testcase_01	AC	2 ms; 5,248 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	3 ms; 5,376 KB
testcase_05	AC	6 ms; 5,376 KB
testcase_06	AC	9 ms; 5,376 KB
testcase_07	AC	7 ms; 5,376 KB
testcase_08	AC	7 ms; 5,376 KB
testcase_09	AC	4 ms; 5,376 KB
testcase_10	AC	33 ms; 5,376 KB
testcase_11	AC	32 ms; 5,376 KB
testcase_12	AC	44 ms; 5,376 KB
testcase_13	AC	33 ms; 5,376 KB
testcase_14	AC	50 ms; 5,376 KB
testcase_15	AC	9 ms; 5,376 KB
testcase_16	AC	111 ms; 6,784 KB
testcase_17	AC	18 ms; 5,376 KB
testcase_18	AC	72 ms; 5,376 KB
testcase_19	AC	150 ms; 6,912 KB
testcase_20	AC	116 ms; 6,144 KB
testcase_21	AC	13 ms; 5,376 KB
testcase_22	AC	87 ms; 5,376 KB
testcase_23	AC	246 ms; 7,808 KB
testcase_24	AC	244 ms; 7,808 KB
testcase_25	TLE	-

ソースコード

#include <iostream>
#include <cassert>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <deque>

using namespace std;
typedef pair<int, deque<int>> P;

int main() {
  int N, M; cin >> N >> M;
  
  vector<int> A(M);
  for (int &a: A) cin >> a;
  
  auto compare = [](P a, P b) {
    if (a.second.size() != b.second.size())
      return a.second.size() < b.second.size();
    return a.first > b.first;
  };
  
  priority_queue<P, vector<P>, decltype(compare)> que {compare};

  for (int i = 0; i < N; i++) {
    deque<int> h;
    for (int j = 0; j < M; j++) {
      int T; cin >> T;
      h.push_back(T);
    }
    que.push(make_pair(i, h));
  }

  map<int, int> mp;

  vector<int> ans(N);
  while (!que.empty()) {
    P nxt = que.top(); que.pop();
    int h = nxt.second.front(); nxt.second.pop_front();

    if (mp[h] < A[h]) {
      mp[h]++;
      ans[nxt.first] = h;
    } else {
      que.push(make_pair(nxt.first, nxt.second));
    }
  }

  for (int i = 0; i < N; i++) {
    cout << ans[i] << (i + 1 == N? '\n': ' ');
  }
  return 0;
}