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

• 問題: No.2680 研究室配属
• ユーザー: kekenx
• 提出日時: 2024-05-26 23:22:17
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: TLE
• 実行時間: -
• コード長: 1,192 bytes
• コンパイル時間: 1,445 ms
• コンパイル使用メモリ: 109,368 KB
• 実行使用メモリ: 14,620 KB
• 最終ジャッジ日時: 2024-05-26 23:22:25
• 合計ジャッジ時間: 7,624 ms
• ジャッジサーバーID （参考情報）: judge5 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 13,884 KB
testcase_01	AC	2 ms; 6,940 KB
testcase_02	AC	2 ms; 6,944 KB
testcase_03	AC	2 ms; 6,940 KB
testcase_04	AC	2 ms; 6,944 KB
testcase_05	AC	6 ms; 6,940 KB
testcase_06	AC	7 ms; 6,940 KB
testcase_07	AC	8 ms; 6,940 KB
testcase_08	AC	7 ms; 6,940 KB
testcase_09	AC	5 ms; 6,944 KB
testcase_10	AC	30 ms; 6,944 KB
testcase_11	AC	29 ms; 6,940 KB
testcase_12	AC	41 ms; 6,940 KB
testcase_13	AC	30 ms; 6,944 KB
testcase_14	AC	44 ms; 6,940 KB
testcase_15	AC	8 ms; 6,940 KB
testcase_16	AC	100 ms; 6,944 KB
testcase_17	AC	21 ms; 6,944 KB
testcase_18	AC	59 ms; 6,940 KB
testcase_19	AC	129 ms; 6,940 KB
testcase_20	AC	102 ms; 6,940 KB
testcase_21	AC	12 ms; 6,944 KB
testcase_22	AC	73 ms; 6,944 KB
testcase_23	AC	215 ms; 7,680 KB
testcase_24	AC	216 ms; 7,936 KB
testcase_25	TLE	-

ソースコード

#include <iostream>
#include <cassert>
#include <vector>
#include <unordered_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));
  }

  unordered_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 {
      while (mp[nxt.second.front()] >= A[nxt.second.front()]) {
	nxt.second.pop_front();
      }
      que.push(make_pair(nxt.first, nxt.second));
    }
  }

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