Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.*;
- /**
- * @author iisaev
- */
- public class OneMax {
- private static final Random RANDOM = new Random();
- private static final int SAMPLE_SIZE = 10;
- private static final FastScanner IN = new FastScanner();
- private static final PrintWriter OUT = new PrintWriter(new BufferedOutputStream(System.out));
- private final int N;
- private OneMax(int n) {
- this.N = n;
- }
- public static void main(final String[] args) {
- new OneMax(IN.nextInt()).run();
- }
- private void run() {
- int fitness = IN.nextInt();
- //int fitness = server.getClueFitness();
- int position = 0;
- while (position < N && fitness < N) {
- final int sampleLength = Math.min(SAMPLE_SIZE, N - position);
- fitness = processSample(position, sampleLength, fitness);
- position += sampleLength;
- }
- }
- private int processSample(final int position,
- final int sampleLength,
- final int prevFitness) {
- final BitSet revertAll = new BitSet();
- revertAll.set(0, sampleLength);
- // we need to find out fitness of the current sample
- final int fitnessOfReversedSample = propose(revertAll, position);
- if (fitnessOfReversedSample == N) {
- return fitnessOfReversedSample; // we somehow found correct result
- }
- final int fitnessOfRemainder = (prevFitness + fitnessOfReversedSample - sampleLength) / 2;
- if (fitnessOfReversedSample - fitnessOfRemainder == sampleLength) {
- return fitnessOfReversedSample;
- }
- BitSet prevGuess = new BitSet(sampleLength);
- prevGuess.set(0, sampleLength); // all ones
- final List<BitSet> permutations = generatePermutationsButLast(sampleLength);
- int fitness = 0;
- while (fitness != sampleLength) {
- final BitSet guess = permutations.get(RANDOM.nextInt(permutations.size()));
- final BitSet bitsToChange = (BitSet) guess.clone();
- bitsToChange.xor(prevGuess);
- fitness = propose(bitsToChange, position) - fitnessOfRemainder;
- final int currentFitness = fitness;
- permutations.removeIf(bitSet -> fitness(guess, bitSet, sampleLength) != currentFitness);
- prevGuess = guess;
- }
- return fitness + fitnessOfRemainder;
- }
- private int propose(final BitSet bitsToFlip,
- final int sampleStart) {
- int position = 0;
- int bitToPrint = bitsToFlip.nextSetBit(position);
- StringBuilder sb = new StringBuilder();
- while (bitToPrint != -1) {
- sb.append(bitToPrint + sampleStart + 1);
- sb.append(" ");
- position = bitToPrint + 1;
- bitToPrint = bitsToFlip.nextSetBit(position);
- }
- OUT.println(sb.toString());
- OUT.flush();
- return IN.nextInt();
- }
- public static int fitness(final BitSet guess,
- final BitSet bitSet,
- final int sampleLength) {
- final BitSet copy = (BitSet) guess.clone();
- copy.xor(bitSet);
- copy.flip(0, sampleLength);
- return copy.cardinality();
- }
- private List<BitSet> generatePermutationsButLast(final int sampleLength) {
- final int numberOfPerms = (1 << sampleLength) - 1;
- final List<BitSet> permutations = new ArrayList<>(numberOfPerms);
- for (int i = 0; i < numberOfPerms; ++i) {
- permutations.add(BitSet.valueOf(new long[] {i}));
- }
- return permutations;
- }
- public static class FastScanner {
- BufferedReader br;
- StringTokenizer st;
- public FastScanner() {
- br = new BufferedReader(new InputStreamReader(System.in));
- }
- String next() {
- while (st == null || !st.hasMoreElements()) {
- try {
- st = new StringTokenizer(br.readLine());
- } catch (IOException e) {
- e.printStackTrace();
- }
- }
- return st.nextToken();
- }
- int nextInt() {
- return Integer.parseInt(next());
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement