#411542 (Scala(Beta)) No.953 席

提出ソース

結果

問題	No.953 席
ユーザー	yakamoto
提出日時	2019-12-24 01:07:17
言語	Scala(Beta) (3.4.0)
結果	TLE
実行時間	-
コード長	8,761 bytes
コンパイル時間	12,417 ms
コンパイル使用メモリ	265,284 KB
実行使用メモリ	96,224 KB
最終ジャッジ日時	2023-10-19 09:24:19
合計ジャッジ時間	70,047 ms
ジャッジサーバーID （参考情報）	judge13 / judge11

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	973 ms 65,736 KB
testcase_01	AC	975 ms 65,764 KB
testcase_02	TLE	-
testcase_03	AC	1,867 ms 74,032 KB
testcase_04	TLE	-
testcase_05	AC	1,785 ms 71,508 KB
testcase_06	TLE	-
testcase_07	AC	1,842 ms 82,008 KB
testcase_08	TLE	-
testcase_09	AC	1,769 ms 78,864 KB
testcase_10	AC	1,484 ms 71,428 KB
testcase_11	AC	1,964 ms 83,888 KB
testcase_12	TLE	-
testcase_13	TLE	-
testcase_14	TLE	-
testcase_15	TLE	-
testcase_16	TLE	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	TLE	-
testcase_23	TLE	-
testcase_24	TLE	-
testcase_25	TLE	-
testcase_26	TLE	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

object Main {
  import java.io.{BufferedReader, InputStream, InputStreamReader}
  import java.util.StringTokenizer
  import scala.reflect.ClassTag

  def main(args: Array[String]): Unit = {
    val out = new java.io.PrintWriter(System.out)
    new Main(out, new InputReader(System.in)).solve()
    out.flush()
  }

  private[this] val oj = System.getenv("MY_DEBUG") == null
  def DEBUG(f: => Unit): Unit = {
    if (!oj){ f }
  }
  def debug(as: Array[Boolean]): Unit = if (!oj){ debug(as.map(x => if(x) "1" else "0").mkString) }
  def debug(as: Array[Int]): Unit = if (!oj){ debug(as.mkString(" ")) }
  def debug(as: Array[Long]): Unit =if (!oj){ debug(as.mkString(" ")) }
  def debugDim(m: Array[Array[Int]]): Unit = if (!oj){
    REP(m.length) { i =>
      debug(m(i))
    }
  }
  def debugDimFlip(m: Array[Array[Long]]): Unit = if (!oj){
    REP(m(0).length) { j =>
      REP(m.length) { i =>
        System.err.print(m(i)(j))
        System.err.print(" ")
      }
      System.err.println()
    }
  }
  def debug(s: => String): Unit = {
    if (!oj){ System.err.println(s) }
  }
  def isDebug[A](debug: => A, online: => A): A = {
    if (oj) online else debug
  }

  class InputReader(val stream: InputStream) {
    private[this] val reader = new BufferedReader(new InputStreamReader(stream), 32768)
    private[this] var tokenizer: StringTokenizer = _

    private[this] def next(): String = {
      while (tokenizer == null || !tokenizer.hasMoreTokens)
        tokenizer = new StringTokenizer(reader.readLine)
      tokenizer.nextToken
    }

    def nextInt(): Int = Integer.parseInt(next())
    def nextLong(): Long = java.lang.Long.parseLong(next())
    def nextChar(): Char = next().charAt(0)

    def ni(): Int = nextInt()
    def nl(): Long = nextLong()
    def nc(): Char = nextChar()
    def ns(): String = next()
    def ns(n: Int): Array[Char] = ns().toCharArray
    def na(n: Int, offset: Int = 0): Array[Int] = map(n)(_ => ni() + offset)
    def na2(n: Int, offset: Int = 0): (Array[Int], Array[Int]) = {
      val A1, A2 = Array.ofDim[Int](n)
      REP(n) { i =>
        A1(i) = ni() + offset
        A2(i) = ni() + offset
      }
      (A1, A2)
    }
    def nm(n: Int, m: Int): Array[Array[Int]] = {
      val A = Array.ofDim[Int](n, m)
      REP(n) { i =>
        REP(m) { j =>
          A(i)(j) = ni()
        }
      }
      A
    }
    def nal(n: Int): Array[Long] = map(n)(_ => nl())
    def nm_c(n: Int, m: Int): Array[Array[Char]] = map(n) (_ => ns(m))
  }

  def REP(n: Int, offset: Int = 0)(f: Int => Unit): Unit = {
    var i = offset
    val N = n + offset
    while(i < N) { f(i); i += 1 }
  }
  def REP_r(n: Int, offset: Int = 0)(f: Int => Unit): Unit = {
    var i = n - 1 + offset
    while(i >= offset) { f(i); i -= 1 }
  }
  def TO(from: Int, to: Int)(f: Int => Unit): Unit = {
    REP(to - from + 1, from)(f)
  }
  def map[@specialized A: ClassTag](n: Int, offset: Int = 0)(f: Int => A): Array[A] = {
    val res = Array.ofDim[A](n)
    REP(n)(i => res(i) = f(i + offset))
    res
  }

  def sumL(as: Array[Int]): Long = {
    var s = 0L
    REP(as.length)(i => s += as(i))
    s
  }
  def cumSum(as: Array[Int]): Array[Long] = {
    val cum = Array.ofDim[Long](as.length + 1)
    REP(as.length) { i =>
      cum(i + 1) = cum(i) + as(i)
    }
    cum
  }
}

object Workspace {
  import Main._
  import java.util.Arrays.sort

  import scala.collection.mutable
  import math.{abs, max, min}
  import mutable.ArrayBuffer

  class BIT(n: Int, zero: Int)(f: (Int, Int) => Int) {
    def this(n: Int) = this(n, 0)(_ + _)

    private val N = {
      val a = Integer.highestOneBit(n)
      if (a == n) a else a << 1
    }
    private val bit = if (zero != 0) Array.fill[Int](N + 1)(zero) else Array.ofDim[Int](N + 1)

    /**
      * 1 index
      * addとindex違うよ
      * cumsumなんかといっしょ
      */
    def sum(i: Int): Int = {
      assert(i <= n)
      var x = i
      var s: Int = zero
      while(x > 0) {
        s = f(s, bit(x))
        x -= x & -x
      }
      s
    }

    /**
      * 0 index
      */
    def add(i: Int, a: Int): Unit = {
      assert(i < n)
      var x = i + 1
      while(x <= N) {
        bit(x) = f(bit(x), a)
        x += x & -x
      }
    }

    def sumAll: Int = sum(n)

    // A がLongとかじゃない場合はこれらを実装しないと下の奴らが使えない
    private def sub(a: Int, b: Int) = a - b
    private def lt(a: Int, b: Int) = a < b

    /**
      * [l, r)
      */
    def query(l: Int, r: Int): Int = {
      assert(r > l)
      sub(sum(r), sum(l))
    }

    def query(i: Int): Int = {
      query(i, i + 1)
    }

    def lowerBound(W: Int): Int = {
      var k = N
      var x = 0
      var w = W
      while(k > 0) {
        if (x + k <= N && lt(bit(x + k), w)) {
          w = sub(w, bit(x + k))
          x += k
        }
        k /= 2
      }
      math.min(n, x)
    }
  }
}

class Main(out: java.io.PrintWriter, sc: Main.InputReader) {
  import sc._
  import Main._
  import java.util.Arrays.sort

  import scala.collection.mutable
  import math.{abs, max, min}
  import mutable.ArrayBuffer
  import Workspace._

  // toIntとか+7とかするならvalにしろ
  final private[this] val MOD = 1000000007

  def solve(): Unit = {
    import java.util
    import java.util.Comparator
    val N = ni()
    val K1, K2 = ni() - 1
    val Q = ni()
    val (a, b) = na2(Q)
    val queue = new util.ArrayDeque[Integer] // id
    val returns = new java.util.TreeMap[Long, ArrayBuffer[Int]]
    val seatNo = Array.ofDim[Int](N) // 近い順 -> 席順
    val toNearlest = Array.ofDim[Int](N) // 席順 -> 近い順
    val available = Array.fill[Boolean](N)(true) // 席順
    val vacant = new BIT(N) // 近い順
    val vacant3 = new BIT(N) // 近い順
    def init() = {
      REP(N) { i =>
        vacant.add(i, 1)
        vacant3.add(i, 1)
      }

      var lst = 0 // 0: l, 1: r
      var l, r = K1
      var i = 1
      seatNo(0) = K1
      toNearlest(K1) = 0
      if (K1 < K2) {
        lst = 0
      } else {
        lst = 1
      }

      while (i < N) {
        lst = if (lst == 0) {
          if (r < N - 1) 1 else 0
        } else {
          if (l > 0) 0 else 1
        }
        if (lst == 0) {
          l -= 1
          seatNo(i) = l
          toNearlest(l) = i
        } else {
          r += 1
          seatNo(i) = r
          toNearlest(r) = i
        }

        i += 1
      }
    }

    init()
    debug(seatNo)
    debug(toNearlest)

    def test3(seat: Int): Boolean = {
      var ok = true
      TO(max(seat-1, 0), min(seat+1, N - 1)) { i =>
        ok &&= available(i)
      }
      ok
    }

    def occupy(seat: Int): Unit = {
      available(seat) = false
      vacant.add(toNearlest(seat), -1)
      if (vacant3.query(toNearlest(seat)) == 1) {
        vacant3.add(toNearlest(seat), -1)
      }
      if (seat > 0 && vacant3.query(toNearlest(seat-1)) == 1) {
        vacant3.add(toNearlest(seat-1), -1)
      }
      if (seat < N - 1 && vacant3.query(toNearlest(seat+1)) == 1) {
        vacant3.add(toNearlest(seat+1), -1)
      }
    }

    def empty(seat: Int): Unit = {
      available(seat) = true
      vacant.add(toNearlest(seat), 1)
      if (test3(seat)) {
        vacant3.add(toNearlest(seat), 1)
      }
      if (seat > 0 && test3(seat-1)) {
        vacant3.add(toNearlest(seat-1), 1)
      }
      if (seat < N - 1 && test3(seat+1)) {
        vacant3.add(toNearlest(seat+1), 1)
      }
    }

    val ans = Array.ofDim[Int](Q)

    def processQueue(t: Long): Unit = {
      if (!queue.isEmpty) {
        var nearestSeat = vacant3.lowerBound(1)
        if (nearestSeat == N) {
          nearestSeat = vacant.lowerBound(1)
        }

        debug(s"processQueue nearestSeat:$nearestSeat")

        // 座ることができた
        if (nearestSeat < N) {
          val id = queue.poll()
          val seat = seatNo(nearestSeat)
          occupy(seat)
          val ret = t + b(id)
          if (!returns.containsKey(ret)) {
            returns.put(ret, ArrayBuffer())
          }
          returns.get(ret) += seat
          ans(id) = seat + 1
        }
      }
    }

    def processReturn(to: Long): Unit = {
      while(!returns.isEmpty && returns.firstKey <= to) {
        val e = returns.pollFirstEntry()
        debug(s"return t:${e.getKey} seats=[${e.getValue.mkString(",")}]")
        e.getValue.foreach(empty)

        // 席を空けた時間ごとにqueueを処理する
        processQueue(e.getKey)
      }
    }

    REP(Q) { i =>
      // 帰る時間になっていたら帰る
      processReturn(a(i))
      queue.add(i)
      processQueue(a(i))
    }
    // queueの処理
    processReturn(Long.MaxValue)

    assert(ans.count(_ == 0) == 0)

    ans.foreach(out.println)
  }
}

yukicoder

結果

テストケース

ソースコード