Advertisement
Guest User

D

a guest
Jun 6th, 2014
326
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.78 KB | None | 0 0
  1. import java.io.InputStreamReader;
  2. import java.io.IOException;
  3. import java.util.ArrayList;
  4. import java.io.BufferedReader;
  5. import java.io.OutputStream;
  6. import java.io.PrintWriter;
  7. import java.util.StringTokenizer;
  8. import java.io.InputStream;
  9.  
  10. /**
  11.  * Built using CHelper plug-in
  12.  * Actual solution is at the top
  13.  */
  14. public class Main {
  15.     public static void main(String[] args) {
  16.         InputStream inputStream = System.in;
  17.         OutputStream outputStream = System.out;
  18.         InputReader in = new InputReader(inputStream);
  19.         PrintWriter out = new PrintWriter(outputStream);
  20.         ProblemD solver = new ProblemD();
  21.         solver.solve(1, in, out);
  22.         out.close();
  23.     }
  24. }
  25.  
  26. class ProblemD {
  27.     public void solve(int testNumber, InputReader in, PrintWriter out) {
  28.         int k = in.nextInt();
  29.         int left = 0;
  30.         int right = 100001;
  31.         while (right - left > 1){
  32.             int mid = (right + left) / 2;
  33.             long inv = ((long)mid*(mid - 1)) / 2;
  34.             if (inv >= k)right = mid;
  35.             else left = mid;
  36.         }
  37.         long inversion = ((long)right*(right - 1)) / 2;
  38.         int []ar = new int[right + 1];
  39.         boolean []over = new boolean[right + 1];
  40.         int z = 0;
  41.         ArrayList<Integer> arrayList = new ArrayList<Integer>();
  42.         while (inversion > k){
  43.             int lo = 0;
  44.             int hi = right + 1;
  45.             while (hi - lo > 1){
  46.                 int mid = (hi + lo) / 2;
  47.                 long dif = inversion - (right - mid);
  48.                 if (dif >= k)hi = mid;
  49.                 else lo = mid;
  50.             }
  51.             while (inversion - (right - hi) < k)hi--;
  52.             arrayList.add(hi);
  53.             over[hi] = true;
  54.             inversion -= (right - hi);
  55.         }
  56.         out.print(right+"\n");
  57.         int s = right - arrayList.size();
  58.         for (int i = 0; i < arrayList.size(); i++) {
  59.             out.print(arrayList.get(i)+" ");
  60.         }
  61.         for (int i = right; i >= 1 ; i--) {
  62.             if (over[i])continue;
  63.             out.print(i);
  64.             if (s > 0){
  65.                 out.print(" ");
  66.                 s--;
  67.             }
  68.         }
  69.  
  70.     }
  71. }
  72.  
  73. class InputReader {
  74.     public BufferedReader reader;
  75.     public StringTokenizer tokenizer;
  76.  
  77.     public InputReader(InputStream stream) {
  78.         reader = new BufferedReader(new InputStreamReader(stream));
  79.         tokenizer = null;
  80.     }
  81.  
  82.     public String next() {
  83.         while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  84.             try {
  85.                 tokenizer = new StringTokenizer(reader.readLine());
  86.             } catch (IOException e) {
  87.                 throw new RuntimeException(e);
  88.             }
  89.         }
  90.         return tokenizer.nextToken();
  91.     }
  92.  
  93.     public int nextInt() {
  94.         return Integer.parseInt(next());
  95.     }
  96.  
  97.  
  98. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement