Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import random
- def request(offset, query, new_query, chunk_len):
- [print(offset + pos + 1, end=' ') for pos in range(0, chunk_len) if (query ^ new_query) & (1 << pos)]
- print(flush=True)
- return int(input())
- def find_chunk(n, offset, fitness, out_fitness):
- def remove_from_suitable_queries(suitable_queries, query, fitness):
- return [q for q in suitable_queries if (bin(2**n - 1 - (query ^ q)).count("1")) == fitness]
- query = (1 << n) - 1
- suitable_queries = remove_from_suitable_queries(list(range(0, 2**n)), query, fitness)
- new_fitness = fitness
- while len(suitable_queries) > 1:
- new_query = random.choice(suitable_queries)
- new_fitness = request(offset, query, new_query, n) - out_fitness
- suitable_queries = remove_from_suitable_queries(suitable_queries, new_query, new_fitness)
- query = new_query
- if new_fitness != n:
- request(offset, query, suitable_queries[0], n)
- n, fitness = tuple(int(x) for x in input().split())
- chunk_len = 8
- for i in range(0, int(n / chunk_len) + 1):
- if fitness == n:
- break
- step = min(chunk_len, n - i * chunk_len)
- offset = i * chunk_len
- new_fitness = request(offset, 0, (1 << step) - 1, step)
- chunk_fitness = int((step + new_fitness - fitness) / 2)
- find_chunk(step, offset, chunk_fitness, new_fitness - chunk_fitness)
- fitness = new_fitness - chunk_fitness + step
Add Comment
Please, Sign In to add comment