Advertisement
Guest User

Untitled

a guest
Jun 25th, 2013
225
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.15 KB | None | 0 0
  1.  
  2. import java.io.*;
  3. import java.util.*;
  4.  
  5. public class Main {
  6.     public static void main(String[] args) throws Exception {
  7.         long time = System.nanoTime();
  8.  
  9.         int n = 100000;
  10.         int[] x = new int[n];
  11.         for(int i = 0; i < n; i++){
  12.             x[i] = n-i;
  13.         }
  14.         int[] next = new int[n];
  15.         for (int i = 0; i < n - 1; i++) next[i] = i + 1;
  16.         next[n - 1] = -1;
  17.  
  18.         int count = 0;
  19.         ArrayList<Integer> eat = new ArrayList<Integer>();
  20.         for (int i = 0; i < n; i++) eat.add(i);
  21.         while (true) {
  22.             ArrayList<Integer> neweat = new ArrayList<Integer>();
  23.             for (int start : eat) {
  24.                 boolean flag = false;
  25.                 int xx = start;
  26.                 while (true) {
  27.                     int yy = next[xx];
  28.                     if (yy == -1 || x[yy] > x[xx]) {
  29.                         next[start] = yy;
  30.                         break;
  31.                     }
  32.                     xx = yy;
  33.                     flag = true;
  34.                 }
  35.                 if (flag) neweat.add(start);
  36.             }
  37.             if (neweat.size() != 0) count++;
  38.             else break;
  39.             eat = neweat;
  40. //          System.out.println(eat.size());
  41.         }
  42.  
  43.         out.println(count);
  44.        
  45. ///     System.out.println((System.nanoTime() - time)* 1e-9);
  46.         out.close();
  47.     }
  48.     static PrintWriter out = new PrintWriter(System.out);
  49.    
  50.     static BufferedReader bufferedreader = new BufferedReader(new InputStreamReader(System.in));
  51.     static StringTokenizer in = new StringTokenizer("");
  52.  
  53.     static String nextToken() throws Exception {
  54.         if (!in.hasMoreTokens()) in = new StringTokenizer(bufferedreader.readLine());
  55.         return in.nextToken();
  56.     }
  57.  
  58.     static int next()  throws Exception {return Integer.parseInt(nextToken());};
  59.     static int[] next(int n) throws Exception {
  60.         int[] x = new int[n];
  61.         for (int i = 0; i < n; i++) x[i] = next();
  62.         return x;
  63.     }
  64.     static int[][] next(int n, int m) throws Exception {
  65.         int[][] x = new int[n][];
  66.         for (int i = 0; i < n; i++) x[i] = next(m);
  67.         return x;
  68.     }
  69.  
  70.     static long nextl() throws Exception {return Long.parseLong(nextToken());};
  71.     static long[] nextl(int n) throws Exception {
  72.         long[] x = new long[n];
  73.         for (int i = 0; i < n; i++) x[i] = nextl();
  74.         return x;
  75.     }
  76.     static long[][] nextl(int n, int m) throws Exception {
  77.         long[][] x = new long[n][];
  78.         for (int i = 0; i < n; i++) x[i] = nextl(m);
  79.         return x;
  80.     }
  81.  
  82.     static double nextd() throws Exception {return Double.parseDouble(nextToken());};
  83.     static double[] nextd(int n) throws Exception {
  84.         double[] x = new double[n];
  85.         for (int i = 0; i < n; i++) x[i] = nextd();
  86.         return x;
  87.     }
  88.     static double[][] nextd(int n, int m) throws Exception {
  89.         double[][] x = new double[n][];
  90.         for (int i = 0; i < n; i++) x[i] = nextd(m);
  91.         return x;
  92.     }
  93.  
  94.     static String nextline() throws Exception {
  95.         in = new StringTokenizer("");
  96.         return bufferedreader.readLine();
  97.     }
  98.  
  99. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement