Advertisement
Guest User

Codechef: Lucky Draw

a guest
Sep 21st, 2014
337
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.42 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.Arrays;
  3. import java.util.InputMismatchException;
  4.  
  5. /**
  6. * Created by sijhanwa on 9/21/14.
  7. */
  8. public class D2 {
  9.  
  10.  
  11. private static int getCiel(int a[],int val,int l, int r){
  12. int m = 0;
  13. while (l<r-1){
  14. m = l+(r-l)/2;
  15. if(a[m]>val){
  16. r = m;
  17. }else{
  18. l=m;
  19. }
  20.  
  21. }
  22. return r;
  23.  
  24.  
  25. }
  26.  
  27. private static int getLIS(int[] a, int startIndex,int N) {
  28. int length = 1;
  29. int [] lists = new int[a.length-1];
  30. lists[0] = a[startIndex];
  31.  
  32. for (int i = 1;i<N;i++){
  33. if(a[i+startIndex]<lists[0]){
  34. lists[0]=a[i+startIndex];
  35. }
  36. else if(a[i+startIndex]>lists[length-1]){
  37. lists[length++]=a[i+startIndex];
  38. }
  39. else{
  40. lists[getCiel(lists,a[i+startIndex],0,length-1)] = a[i+startIndex];
  41.  
  42. }
  43.  
  44. }
  45.  
  46.  
  47. return length;
  48. }
  49.  
  50.  
  51. public static void main(String[] args) throws IOException {
  52. BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  53. PrintWriter pw = new PrintWriter(System.out);
  54. InputReader in = new InputReader(System.in);
  55.  
  56. int TC = in.readInt();
  57. while (TC-- > 0) {
  58. int N = in.readInt();
  59. int [] numbers = new int[2*N+1];
  60. for(int i = 0;i<N;i++){
  61. numbers[i] = in.readInt();
  62. numbers[i+N] = numbers[i];
  63. }
  64.  
  65. int max = 0;
  66. for(int i = 0;i<N;i++){
  67.  
  68. max = max(max,getLIS(numbers,i,N));
  69.  
  70. }
  71.  
  72.  
  73.  
  74. pw.println(max);
  75. }
  76. pw.flush();
  77. pw.close();
  78. }
  79.  
  80. private static int max(int n1, int n2) {
  81.  
  82. return (n1>n2?n1:n2);
  83. }
  84.  
  85. private static int min(int n1, int n2) {
  86.  
  87. return (n1<n2?n1:n2);
  88. }
  89.  
  90.  
  91. }
  92. /*
  93. //initialize
  94. InputReader in = new InputReader(System.in);
  95. OutputWriter out = new OutputWriter(System.out);
  96.  
  97. //read int
  98. int i = in.readInt();
  99.  
  100. //read string
  101. String s = in.readString();
  102.  
  103. //read int array of size N
  104. int[] x = IOUtils.readIntArray(in,N);
  105.  
  106. //printline
  107. out.printLine("X");
  108.  
  109. //flush output
  110. out.flush();
  111.  
  112. //remember to close the
  113. //outputstream, at the end
  114. out.close();
  115.  
  116. */
  117.  
  118. class InputReader {
  119.  
  120.  
  121. private InputStream stream;
  122.  
  123. private byte[] buf = new byte[1024];
  124.  
  125. private int curChar;
  126.  
  127. private int numChars;
  128.  
  129. private SpaceCharFilter filter;
  130.  
  131.  
  132. public InputReader(InputStream stream) {
  133.  
  134. this.stream = stream;
  135.  
  136. }
  137.  
  138.  
  139. public int read() {
  140.  
  141. if (numChars == -1)
  142.  
  143. throw new InputMismatchException();
  144.  
  145. if (curChar >= numChars) {
  146.  
  147. curChar = 0;
  148.  
  149. try {
  150.  
  151. numChars = stream.read(buf);
  152.  
  153. } catch (IOException e) {
  154.  
  155. throw new InputMismatchException();
  156.  
  157. }
  158.  
  159. if (numChars <= 0)
  160.  
  161. return -1;
  162.  
  163. }
  164.  
  165. return buf[curChar++];
  166.  
  167. }
  168.  
  169.  
  170. public int readInt() {
  171.  
  172. int c = read();
  173.  
  174. while (isSpaceChar(c))
  175.  
  176. c = read();
  177.  
  178. int sgn = 1;
  179.  
  180. if (c == '-') {
  181.  
  182. sgn = -1;
  183.  
  184. c = read();
  185.  
  186. }
  187.  
  188. int res = 0;
  189.  
  190. do {
  191.  
  192. if (c < '0' || c > '9')
  193.  
  194. throw new InputMismatchException();
  195.  
  196. res *= 10;
  197.  
  198. res += c - '0';
  199.  
  200. c = read();
  201.  
  202. } while (!isSpaceChar(c));
  203.  
  204. return res * sgn;
  205.  
  206. }
  207.  
  208.  
  209. public String readString() {
  210.  
  211. int c = read();
  212.  
  213. while (isSpaceChar(c))
  214.  
  215. c = read();
  216.  
  217. StringBuilder res = new StringBuilder();
  218.  
  219. do {
  220.  
  221. res.appendCodePoint(c);
  222.  
  223. c = read();
  224.  
  225. } while (!isSpaceChar(c));
  226.  
  227. return res.toString();
  228.  
  229. }
  230.  
  231.  
  232. public boolean isSpaceChar(int c) {
  233.  
  234. if (filter != null)
  235.  
  236. return filter.isSpaceChar(c);
  237.  
  238. return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  239.  
  240. }
  241.  
  242.  
  243. public String next() {
  244.  
  245. return readString();
  246.  
  247. }
  248.  
  249.  
  250. public interface SpaceCharFilter {
  251.  
  252. public boolean isSpaceChar(int ch);
  253.  
  254. }
  255.  
  256. }
  257.  
  258.  
  259. class OutputWriter {
  260.  
  261. private final PrintWriter writer;
  262.  
  263.  
  264. public OutputWriter(OutputStream outputStream) {
  265.  
  266. writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
  267.  
  268. }
  269.  
  270.  
  271. public OutputWriter(Writer writer) {
  272.  
  273. this.writer = new PrintWriter(writer);
  274.  
  275. }
  276.  
  277.  
  278. public void print(Object...objects) {
  279.  
  280. for (int i = 0; i < objects.length; i++) {
  281.  
  282. if (i != 0)
  283.  
  284. writer.print(' ');
  285.  
  286. writer.print(objects[i]);
  287.  
  288. }
  289.  
  290. }
  291.  
  292.  
  293. public void printLine(Object...objects) {
  294.  
  295. print(objects);
  296.  
  297. writer.println();
  298.  
  299. }
  300.  
  301.  
  302. public void close() {
  303.  
  304. writer.close();
  305.  
  306. }
  307.  
  308.  
  309. public void flush() {
  310.  
  311. writer.flush();
  312.  
  313. }
  314.  
  315.  
  316. }
  317.  
  318.  
  319. class IOUtils {
  320.  
  321.  
  322. public static int[] readIntArray(InputReader in, int size) {
  323.  
  324. int[] array = new int[size];
  325.  
  326. for (int i = 0; i < size; i++)
  327.  
  328. array[i] = in.readInt();
  329.  
  330. return array;
  331.  
  332. }
  333.  
  334.  
  335. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement