結果

問題 No.953 席
ユーザー tnakao0123tnakao0123
提出日時 2019-12-20 13:56:13
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 3,415 bytes
コンパイル時間 1,007 ms
コンパイル使用メモリ 101,488 KB
実行使用メモリ 9,608 KB
最終ジャッジ日時 2023-09-22 16:52:12
合計ジャッジ時間 7,625 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
8,756 KB
testcase_01 AC 2 ms
4,384 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 TLE -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 953.cc:  No.953 席 - yukicoder
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 100000;
const int MAX_E2 = 1 << 18; // = 262144

enum { LEV, ARV };

/* typedef */

typedef vector<int> vi;
typedef queue<int> qi;

struct Seat {
  int o, d, i;
  Seat() {}
  Seat(int _o, int _d, int _i): o(_o), d(_d), i(_i) {}
  bool operator<(const Seat &s) const {
    return o < s.o || (o == s.o && d < s.d);
  }
};
typedef set<Seat> sset;

struct Event {
  int t, p, d, i;
  Event() {}
  Event(int _t, int _p, int _d, int _i): t(_t), p(_p), d(_d), i(_i) {}

  bool operator<(const Event &e) const {
    return t > e.t || (t == e.t && (p > e.p || (p == e.p && d > e.d)));
  }

  void print() { printf("Ev(%d,%d,%d,%d)\n", t, p, d, i); }
};

/* global variables */

int ds[MAX_N], os[MAX_N];
sset fss;

/* subroutines */

inline int nbr(int n, int i) {
  return ((i > 0 && os[i - 1] > 0) || (i + 1 < n && os[i + 1] > 0)) ? 1 : 0;
}

inline Seat createst(int n, int i) { return Seat(nbr(n, i), ds[i], i); }

inline int assignfreeseat(int n) {
  sset::iterator spt = fss.begin();
  Seat st = *spt;
  int li = st.i - 1, ri = st.i + 1;

  fss.erase(spt);
  if (li >= 0 && ! os[li]) fss.erase(createst(n, li));
  if (ri < n && ! os[ri]) fss.erase(createst(n, ri));

  os[st.i] = 1;
  if (li >= 0 && ! os[li]) fss.insert(createst(n, li));
  if (ri < n && ! os[ri]) fss.insert(createst(n, ri));

  return st.i;
}

/* main */

int main() {
  int n, k1, k2;
  scanf("%d%d%d", &n, &k1, &k2);
  k1--, k2--;

  int dk1 = -1, dk2 = 1;
  if (k1 > k2) dk1 = 1, dk2 = -1;

  for (int p = 0; p < n; k1 += dk1, k2 += dk2) {
    if (k1 >= 0 && k1 < n) ds[k1] = p++;
    if (k2 >= 0 && k2 < n) ds[k2] = p++;
  }
  for (int i = 0; i < n; i++) fss.insert(Seat(0, ds[i], i));
  //for (int i = 0; i < n; i++) printf("%d ", ds[i]); putchar('\n');

  int m;
  scanf("%d", &m);

  priority_queue<Event> q;
  
  while (m--) {
    int a, b;
    scanf("%d%d", &a, &b);
    q.push(Event(a, ARV, b, -1));
  }

  qi wq;
  
  while (! q.empty() || ! wq.empty()) {
    // Leave
    int prvt = -1;
    while (! q.empty() && q.top().p == LEV &&
	   (prvt < 0 || q.top().t == prvt)) {
      Event e = q.top(); q.pop();
      //e.print();

      int li = e.i - 1, ri = e.i + 1;
      if (li >= 0 && ! os[li]) fss.erase(createst(n, li));
      if (ri < n && ! os[ri]) fss.erase(createst(n, ri));

      os[e.i] = 0;
      fss.insert(createst(n, e.i));
      if (li >= 0 && ! os[li]) fss.insert(createst(n, li));
      if (ri < n && ! os[ri]) fss.insert(createst(n, ri));

      prvt = e.t;
    }

    // wait queue
    if (prvt >= 0)
      while (! wq.empty() && ! fss.empty()) {
	int i = assignfreeseat(n);
	printf("%d\n", i + 1);

	int b = wq.front(); wq.pop();
	q.push(Event(prvt + b, LEV, ds[i], i));
      }

    // arrive
    while (! q.empty() && q.top().p == ARV) {
      Event e = q.top(); q.pop();
      //e.print();

      if (! fss.empty()) {
	int i = assignfreeseat(n);
	printf("%d\n", i + 1);

	q.push(Event(e.t + e.d, LEV, ds[i], i));
      }
      else {
	wq.push(e.d);
      }
    }
  }
  return 0;
}
0