Submission #1050143
Source Code Expand
k, m = map(int, raw_input().split()) A = map(int, raw_input().split()) Ck = map(int, raw_input().split())[::-1] def nxt(C): C1 = [0]*k C1[0] = C[k-1] & Ck[0] for i in xrange(1, k): C1[i] = C[i-1] ^ (C[k-1] & Ck[i]) return C1 def dbl(C): Ci = C[:] C1 = [0]*k for j in xrange(k): for i in xrange(k): C1[i] ^= C[j] & Ci[i] Ci = nxt(Ci) return C1 def solve(m): if m <= k: return A[m-1] def dfs(m): if m < k: C = [0]*k C[m] = 2**32 - 1 return C C = dbl(dfs(m / 2)) if m % 2 == 1: C = nxt(C) return C C = dfs(m-1) res = 0 for i in xrange(k): res ^= C[i] & A[i] return res print solve(m)
Submission Info
Submission Time | |
---|---|
Task | D - 漸化式 |
User | yaketake08 |
Language | Python (2.7.3) |
Score | 100 |
Code Size | 806 Byte |
Status | AC |
Exec Time | 106 ms |
Memory | 3572 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 100 / 100 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, small_1.txt, small_2.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
random_01.txt | AC | 40 ms | 3536 KB |
random_02.txt | AC | 40 ms | 3572 KB |
random_03.txt | AC | 39 ms | 3440 KB |
random_04.txt | AC | 39 ms | 3440 KB |
random_05.txt | AC | 39 ms | 3440 KB |
random_06.txt | AC | 40 ms | 3452 KB |
random_07.txt | AC | 47 ms | 3488 KB |
random_08.txt | AC | 58 ms | 3456 KB |
random_09.txt | AC | 104 ms | 3488 KB |
random_10.txt | AC | 103 ms | 3492 KB |
random_11.txt | AC | 105 ms | 3452 KB |
random_12.txt | AC | 105 ms | 3452 KB |
random_13.txt | AC | 105 ms | 3452 KB |
random_14.txt | AC | 106 ms | 3568 KB |
random_15.txt | AC | 103 ms | 3572 KB |
sample_1.txt | AC | 40 ms | 3572 KB |
sample_2.txt | AC | 39 ms | 3452 KB |
sample_3.txt | AC | 44 ms | 3452 KB |
small_1.txt | AC | 39 ms | 3452 KB |
small_2.txt | AC | 38 ms | 3448 KB |