AquaBlitz11

[TASK_020] Toilet

Jun 12th, 2021
700
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 100010;
  6. const int M = 11;
  7.  
  8. int where[N];
  9. bool hasppl[M];
  10. queue<int> Q;
  11.  
  12. int main()
  13. {
  14.     int n, m;
  15.     scanf("%d%d", &n, &m);
  16.  
  17.     // -1 = still in queue, 0 = not in queue/quitted the queue, num = room
  18.     for (int i = 0; i < 2*n; ++i) {
  19.         int t, x;
  20.         scanf("%d%d", &t, &x);
  21.         if (t == 1) {
  22.             where[x] = -1;
  23.             Q.push(x); // enqueue x
  24.         } else if (t == 2) {
  25.             if (where[x] == -1)
  26.                 where[x] = 0;
  27.             hasppl[where[x]] = false;
  28.         } else {
  29.             assert(false); // error
  30.         }
  31.         while (!Q.empty()) {
  32.             x = Q.front();
  33.             if (where[x] == 0) { // if x has already quitted the queue, skip
  34.                 Q.pop();
  35.                 continue;
  36.             }
  37.             assert(where[x] == -1);
  38.             for (int i = 1; i <= m; ++i) { // find the empty toilet with min index
  39.                 if (!hasppl[i]) {
  40.                     hasppl[i] = true;
  41.                     where[x] = i;
  42.                     Q.pop();
  43.                     break;
  44.                 }
  45.             }
  46.             if (where[x] == -1)
  47.                 break;
  48.         }
  49.     }
  50.  
  51.     for (int i = 1; i <= n; ++i)
  52.         printf("%d\n", where[i]);
  53.  
  54.     return 0;
  55. }
RAW Paste Data