Advertisement
Guest User

Untitled

a guest
Jan 17th, 2018
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 4.32 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4.  
  5. /**
  6.  * @author iisaev
  7.  */
  8. public class OneMax {
  9.     private static final Random RANDOM = new Random();
  10.  
  11.     private static final int SAMPLE_SIZE = 10;
  12.  
  13.     private static final FastScanner IN = new FastScanner();
  14.  
  15.     private static final PrintWriter OUT = new PrintWriter(new BufferedOutputStream(System.out));
  16.  
  17.     private final int N;
  18.  
  19.     private OneMax(int n) {
  20.         this.N = n;
  21.     }
  22.  
  23.     public static void main(final String[] args) {
  24.         new OneMax(IN.nextInt()).run();
  25.     }
  26.  
  27.     private void run() {
  28.         int fitness = IN.nextInt();
  29.         //int fitness = server.getClueFitness();
  30.         int position = 0;
  31.         while (position < N && fitness < N) {
  32.             final int sampleLength = Math.min(SAMPLE_SIZE, N - position);
  33.             fitness = processSample(position, sampleLength, fitness);
  34.             position += sampleLength;
  35.         }
  36.     }
  37.  
  38.     private int processSample(final int position,
  39.                               final int sampleLength,
  40.                               final int prevFitness) {
  41.         final BitSet revertAll = new BitSet();
  42.         revertAll.set(0, sampleLength);
  43.         // we need to find out fitness of the current sample
  44.         final int fitnessOfReversedSample = propose(revertAll, position);
  45.         if (fitnessOfReversedSample == N) {
  46.             return fitnessOfReversedSample; // we somehow found correct result
  47.         }
  48.         final int fitnessOfRemainder = (prevFitness + fitnessOfReversedSample - sampleLength) / 2;
  49.         if (fitnessOfReversedSample - fitnessOfRemainder == sampleLength) {
  50.             return fitnessOfReversedSample;
  51.         }
  52.         BitSet prevGuess = new BitSet(sampleLength);
  53.         prevGuess.set(0, sampleLength); // all ones
  54.         final List<BitSet> permutations = generatePermutationsButLast(sampleLength);
  55.         int fitness = 0;
  56.         while (fitness != sampleLength) {
  57.             final BitSet guess = permutations.get(RANDOM.nextInt(permutations.size()));
  58.             final BitSet bitsToChange = (BitSet) guess.clone();
  59.             bitsToChange.xor(prevGuess);
  60.             fitness = propose(bitsToChange, position) - fitnessOfRemainder;
  61.             final int currentFitness = fitness;
  62.             permutations.removeIf(bitSet -> fitness(guess, bitSet, sampleLength) != currentFitness);
  63.             prevGuess = guess;
  64.         }
  65.         return fitness + fitnessOfRemainder;
  66.     }
  67.  
  68.     private int propose(final BitSet bitsToFlip,
  69.                         final int sampleStart) {
  70.         int position = 0;
  71.         int bitToPrint = bitsToFlip.nextSetBit(position);
  72.         StringBuilder sb = new StringBuilder();
  73.         while (bitToPrint != -1) {
  74.             sb.append(bitToPrint + sampleStart + 1);
  75.             sb.append(" ");
  76.             position = bitToPrint + 1;
  77.             bitToPrint = bitsToFlip.nextSetBit(position);
  78.         }
  79.         OUT.println(sb.toString());
  80.         OUT.flush();
  81.         return IN.nextInt();
  82.     }
  83.  
  84.     public static int fitness(final BitSet guess,
  85.                               final BitSet bitSet,
  86.                               final int sampleLength) {
  87.         final BitSet copy = (BitSet) guess.clone();
  88.         copy.xor(bitSet);
  89.         copy.flip(0, sampleLength);
  90.         return copy.cardinality();
  91.     }
  92.  
  93.     private List<BitSet> generatePermutationsButLast(final int sampleLength) {
  94.         final int numberOfPerms = (1 << sampleLength) - 1;
  95.         final List<BitSet> permutations = new ArrayList<>(numberOfPerms);
  96.         for (int i = 0; i < numberOfPerms; ++i) {
  97.             permutations.add(BitSet.valueOf(new long[] {i}));
  98.         }
  99.         return permutations;
  100.     }
  101.  
  102.     public static class FastScanner {
  103.         BufferedReader br;
  104.  
  105.         StringTokenizer st;
  106.  
  107.         public FastScanner() {
  108.             br = new BufferedReader(new InputStreamReader(System.in));
  109.         }
  110.  
  111.         String next() {
  112.             while (st == null || !st.hasMoreElements()) {
  113.                 try {
  114.                     st = new StringTokenizer(br.readLine());
  115.                 } catch (IOException e) {
  116.                     e.printStackTrace();
  117.                 }
  118.             }
  119.             return st.nextToken();
  120.         }
  121.  
  122.         int nextInt() {
  123.             return Integer.parseInt(next());
  124.         }
  125.  
  126.     }
  127. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement