結果

問題 No.1296 OR or NOR
ユーザー semisagisemisagi
提出日時 2020-11-20 23:14:36
言語 Swift
(5.4.2)
結果
AC  
実行時間 1,823 ms / 3,000 ms
コード長 1,896 bytes
コンパイル時間 2,008 ms
実行使用メモリ 40,228 KB
最終ジャッジ日時 2023-02-23 19:32:49
合計ジャッジ時間 35,671 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
8,104 KB
testcase_01 AC 3 ms
8,172 KB
testcase_02 AC 503 ms
38,660 KB
testcase_03 AC 488 ms
37,924 KB
testcase_04 AC 1,004 ms
39,744 KB
testcase_05 AC 779 ms
39,968 KB
testcase_06 AC 701 ms
39,116 KB
testcase_07 AC 677 ms
36,544 KB
testcase_08 AC 689 ms
38,160 KB
testcase_09 AC 723 ms
37,864 KB
testcase_10 AC 755 ms
38,868 KB
testcase_11 AC 640 ms
39,328 KB
testcase_12 AC 650 ms
37,804 KB
testcase_13 AC 671 ms
38,916 KB
testcase_14 AC 1,823 ms
39,868 KB
testcase_15 AC 1,760 ms
39,964 KB
testcase_16 AC 1,763 ms
39,912 KB
testcase_17 AC 598 ms
39,928 KB
testcase_18 AC 595 ms
39,780 KB
testcase_19 AC 561 ms
39,836 KB
testcase_20 AC 513 ms
34,092 KB
testcase_21 AC 502 ms
35,012 KB
testcase_22 AC 421 ms
35,788 KB
testcase_23 AC 425 ms
35,736 KB
testcase_24 AC 481 ms
35,648 KB
testcase_25 AC 481 ms
33,996 KB
testcase_26 AC 516 ms
34,116 KB
testcase_27 AC 525 ms
34,968 KB
testcase_28 AC 494 ms
35,404 KB
testcase_29 AC 510 ms
34,168 KB
testcase_30 AC 1,815 ms
39,852 KB
testcase_31 AC 1,759 ms
40,048 KB
testcase_32 AC 1,688 ms
39,844 KB
testcase_33 AC 1,717 ms
40,228 KB
testcase_34 AC 1,798 ms
40,196 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

struct Scanner {
    private var elements = [String]()
    private var index = 0

    mutating func peek() -> String {
        while elements.count == index {
            elements = readLine()!.split(separator: " ").map(String.init)
            index = 0
        }
        return elements[index]
    }

    mutating func next() -> String {
        defer { index += 1 }
        return peek()
    }

    mutating func nextInt() -> Int {
        return Int(next())!
    }

    mutating func nextInts(_ n: Int) -> [Int] {
        return (0 ..< n).map { _ in nextInt() }
    }

    mutating func nextDouble() -> Double {
        return Double(next())!
    }
}

extension Int {
    func test(_ k: Int) -> Bool {
        return self >> k & 1 == 1
    }
}

var scanner = Scanner()

let N = scanner.nextInt()
let A = scanner.nextInts(N)
let Q = scanner.nextInt()
let B = scanner.nextInts(Q)

var last = [Int?](repeating: nil, count: 60)
for i in 0 ..< 60 {
    for j in (0 ..< N).reversed() {
        if A[j].test(i) {
            last[i] = j
            break
        }
    }
}

func solve(_ b: Int) -> Int? {
    var constraints = [Int: Bool]()
    for i in last.indices {
        if let last = last[i] {
            if let c = constraints[last] {
                if !b.test(i) != c {
                    return nil
                }
            } else {
                constraints[last] = !b.test(i)
            }
        } else {
            if let c = constraints[0] {
                if b.test(i) != c {
                    return nil
                }
            } else {
                constraints[0] = b.test(i)
            }
        }
    }
    var answer = 0
    var x = false
    for (_, y) in constraints.sorted(by: { $0.key > $1.key }) {
        if x != y {
            answer += 1
            x = y
        }
    }
    return answer
}

for k in 0 ..< Q {
    print(solve(B[k]) ?? -1)
}
0