[gcj] Re: 2020 1B P1 Expogo: solution using bitwise operations. (fails with WA though). Am I wrong with the approach or is just a bug in code?

[Alexander Iskhakov]

>
> Quickly refactored the code:
>

import java.io.{BufferedReader, BufferedWriter, InputStreamReader, 
OutputStreamWriter}
import java.util.Scanner

object Solution {

  private def isPowerOf2(x: Long) = (x & (x - 1L)) == 0L

  /**
   * returns next power of 2 greater then x.
   * Example: nextPowerOf2GreaterThenX(11) = 16
   *
   * @param x
   * @return
   */
  private def nextPowerOf2GreaterThenX(x: Long): Long = {
    var result = 1L
    var arg = x
    while (arg > 0L) {
      arg = arg >> 1L
      result = result << 1L
    }
    result
  }

  private def transform(a: Long) = {
    val xNextPowerOf2 = nextPowerOf2GreaterThenX(a)
    val x1 = xNextPowerOf2 - a
    xNextPowerOf2 | x1
  }

  def main(args: Array[String]): Unit = {
    val outputWriter = new BufferedWriter(new OutputStreamWriter(System.out))
    val in = new Scanner(new BufferedReader(new InputStreamReader(System.in)))

    val t = in.nextLine().toInt

    for (caseNum <- 1 to t) {
      val (x, xWasNegative, y, yWasNegative) = in.nextLine().split(' 
').map(_.toLong) match {
        case Array(x, y) => (Math.abs(x), x < 0, Math.abs(y), y < 0)
      }

      val (resultX: Long, resultY: Long) =
        if ((x & y) == 0L) {
          x -> y
        } else {
          val xTransformed = transform(x)
          if ((xTransformed & y) == 0L) {
            xTransformed -> y
          } else {
            val yTransformed = transform(y)
            if ((x & yTransformed) == 0L) {
              x -> yTransformed
            } else {
              if ((xTransformed & yTransformed) == 0L)
                xTransformed -> yTransformed
              else
                0L -> 0L
            }
          }
        }

      if (resultX == 0L && resultY == 0L || !isPowerOf2((resultX | resultY) + 
1L)) {
        outputWriter.write(s"Case #$caseNum: IMPOSSIBLE\n")
      } else {
        val isXTransformed = resultX != x
        val isYTransformed = resultY != y

        val result = StringBuilder.newBuilder
        var (xP, yP) = resultX -> resultY
        while (xP > 0L || yP > 0L) {
          if ((xP & 1L) == 1L) {
            if (xP == 1L || !isXTransformed)
              result.append(if (xWasNegative) "W" else "E")
            else
              result.append(if (xWasNegative) "E" else "W")
          } else if ((yP & 1L) == 1L) {
            if (yP == 1L || !isYTransformed)
              result.append(if (yWasNegative) "S" else "N")
            else
              result.append(if (yWasNegative) "N" else "S")
          }
          xP = xP >> 1L
          yP = yP >> 1L
        }

        outputWriter.write(s"Case #$caseNum: ${result.mkString}\n")
      }
    }
    outputWriter.close()
  }

} 

-- 
You received this message because you are subscribed to the Google Groups 
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/google-code/a6af3268-eefa-46d4-b284-80fdb2acd666%40googlegroups.com.