Advertisement
Guest User

Untitled

a guest
Apr 7th, 2019
374
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 2.05 KB | None | 0 0
  1. import random
  2. import sys
  3.  
  4.  
  5. def solveInternal(n, b, askFunc):
  6.     questions = [0] * n
  7.     responses = [0] * (n - b)
  8.     for step in [1, 2, 4, 8, 16]:
  9.         q = []
  10.         while len(q) < n:
  11.             for delta in xrange(step):
  12.                 q.append(0)
  13.             for delta in xrange(step):
  14.                 q.append(1)
  15.         q = q[:n]
  16.         assert len(q) == n
  17.         r = askFunc(q)
  18.         assert len(r) == n - b
  19.         for i in xrange(n):
  20.             questions[i] |= q[i] * step
  21.         for i in xrange(n - b):
  22.             responses[i] |= r[i] * step
  23.     result = []
  24.     i = 0
  25.     for r in responses:
  26.         while i < n and questions[i] != r:
  27.             result.append(i)
  28.             i += 1
  29.         i += 1
  30.     while i < n:
  31.         result.append(i)
  32.         i += 1
  33.     return result
  34.  
  35.  
  36. def solve():
  37.     def askIO(a):
  38.         s = "".join(map(str, a))
  39.         print s
  40.         sys.stdout.flush()
  41.         return [int(x) for x in raw_input()]
  42.  
  43.     T = int(raw_input())
  44.     for t in xrange(T):
  45.         n, b, f = map(int, raw_input().split())
  46.         res = solveInternal(n, b, askIO)
  47.         print " ".join(map(str, res))
  48.         sys.stdout.flush()
  49.         response = int(raw_input())
  50.         if response == -1:
  51.             return
  52.  
  53.  
  54. def stress():
  55.     random.seed(322)
  56.     for test in xrange(1000):
  57.         n = 1000
  58.         b = 15
  59.         s = set()
  60.         while len(s) < b:
  61.             s.add(random.randint(0, n - 1))
  62.         ss = sorted(s)
  63.  
  64.         def askEmulator(a):
  65.             assert len(a) == n
  66.             response = []
  67.             for i in xrange(n):
  68.                 if i not in s:
  69.                     response.append(a[i])
  70.             return response
  71.  
  72.         print "TESTING:", n, b, ss
  73.         res = solveInternal(n, b, askEmulator)
  74.         if res != ss:
  75.             print "FAILED:", n, b, ss, "=>", res
  76.             raise Exception()
  77.         else:
  78.             print "PASSED:", n, b, ss, "=>", res
  79.  
  80.     print "OK!"
  81.  
  82.  
  83. def main():
  84.     # stress()
  85.     solve()
  86.  
  87.  
  88. if __name__ == "__main__":
  89.     main()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement