Nevada112

dp9

Apr 27th, 2021 (edited)
216
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.*;import java.lang.*;import java.util.*;
  2. //* --> number of prime numbers less then or equal to x are  -->  x/ln(x)
  3. //* --> String concatenation using the + operator within a loop should be avoided. Since the String object is immutable, each call for concatenation will
  4. // result in a new String object being created.
  5. // THE SIEVE USED HERE WILL RETURN A LIST CONTAINING ALL THE PRIME NUMBERS TILL N
  6.  public class dp9 {static FastScanner sc;static PrintWriter pw;static class FastScanner {InputStreamReader is;BufferedReader br;StringTokenizer st;
  7. public FastScanner() {is = new InputStreamReader(System.in);br = new BufferedReader(is);}
  8. String next() throws Exception {while (st == null || !st.hasMoreElements())st = new StringTokenizer(br.readLine());
  9. return st.nextToken();}int nextInt() throws Exception {return Integer.parseInt(next());}long nextLong() throws Exception {
  10. return Long.parseLong(next());}int[] readArray(int num) throws Exception {int arr[]=new int[num];
  11. for(int i=0;i<num;i++)arr[i]=nextInt();return arr;}String nextLine() throws Exception {return br.readLine();
  12. }} public static boolean power_of_two(int a){if((a&(a-1))==0){ return true;}return false;}
  13. static boolean PS(double x){if (x >= 0) {double i= Math.sqrt(x);if(i%1!=0){
  14. return false;}return ((i * i) == x);}return false;}public static int[] ia(int n){int ar[]=new int[n];
  15. return ar;}public static long[] la(int n){long ar[]=new long[n];return ar;}
  16. public static void print(int ans,int t){System.out.println("Case"+" "+"#"+t+":"+" "+ans);}
  17. static long mod=1000000007;static int max=Integer.MIN_VALUE;static int min=Integer.MAX_VALUE;
  18. public static void sort(long[] arr){//because Arrays.sort() uses quicksort which is dumb
  19. //Collections.sort() uses merge sort
  20. ArrayList<Long> ls = new ArrayList<Long>();for(long x: arr)ls.add(x);Collections.sort(ls);
  21. for(int i=0; i < arr.length; i++)arr[i] = ls.get(i);}public static long fciel(long a, long b) {if (a == 0)  return 0;return (a - 1) / b + 1;}
  22.  static boolean[] is_prime = new boolean[1000001];static ArrayList<Integer> list = new ArrayList<>();
  23. static long n = 1000000;public static void sieve() {Arrays.fill(is_prime, true);
  24. is_prime[0] = is_prime[1] = false;for (int i = 2; i * i <= n; i++) {
  25. if (is_prime[i]) {for (int j = i * i; j <= n; j += i)is_prime[j] = false;}}for (int i = 2; i <= n; i++) {
  26. if (is_prime[i]) {list.add(i);}}}
  27.  
  28.                         // ----------   NCR   ---------- \
  29.  
  30. static int NC=100005;
  31. static long inv[]=new long[NC];
  32. static long fac_inv[]=new long[NC];
  33. static long fac[]=new long[NC];public static void initialize()
  34. {
  35.     long MOD=mod;
  36.    int  i;
  37.     inv[1]=1;
  38.     for(i=2;i<=NC-2;i++)
  39.         inv[i]=(MOD-MOD/i)*inv[(int)MOD%i]%MOD;
  40.     fac[0]=fac[1]=1;
  41.     for(i=2;i<=NC-2;i++)
  42.         fac[i]=i*fac[i-1]%MOD;
  43.     fac_inv[0]=fac_inv[1]=1;
  44.     for(i=2;i<=NC-2;i++)
  45.         fac_inv[i]=inv[i]*fac_inv[i-1]%MOD;
  46. }
  47. public static long  ncr(int  n,int  r)
  48. {
  49.     long MOD=mod;
  50.     if(n<r) return 0;
  51.     return (fac[n]*fac_inv[r]%MOD)*fac_inv[n-r]%MOD;
  52. }
  53.                         // ----------   NCR   ---------- \
  54.  
  55.                        
  56. public static void main(String args[]) throws java.lang.Exception {
  57. sc = new FastScanner();pw = new PrintWriter(System.out);StringBuilder s = new StringBuilder();
  58.  
  59.         int n=sc.nextInt();
  60.         int ar[]=new int[n];
  61.         for(int i=0;i<n;i++){
  62.             ar[i]=sc.nextInt();
  63.         }
  64.         boolean dp[][]=new boolean[n][6];
  65.     for(int i=1;i<=5;i++)
  66.     {
  67.         dp[0][i]=true;
  68.     }
  69. for(int i=1;i<n;i++)
  70. {
  71.     for(int j=1;j<=5;j++)
  72.     {
  73.         if(ar[i]>ar[i-1])
  74.         {
  75.             dp[i][j]=dp[i-1][Math.max(j-1,0)]|dp[i-1][Math.max(j-2,0)]|dp[i-1][Math.max(j-3,0)]|dp[i-1][Math.max(j-4,0)];
  76.         }
  77.         else if(ar[i]<ar[i-1])
  78.         {
  79.             dp[i][j]=dp[i-1][Math.min(j+1,5)]|dp[i-1][Math.min(j+2,5)]|dp[i-1][Math.min(j+3,5)]|dp[i-1][Math.min(j+4,5)];  
  80.         }
  81.         else{
  82.             for(int k=1;k<=5;k++)
  83.             {
  84.                 if(k!=j)
  85.                 {
  86.                 dp[i][j]|=dp[i-1][k];
  87.                 }
  88.             }
  89.         }
  90.     }
  91. }
  92. for(boolean i[]:dp)
  93. {
  94.     for(boolean j:i)
  95.     {System.out.print(j+" ");}
  96.     System.out.println();
  97. }
  98. ArrayList<Integer> list=new ArrayList<>();
  99. for(int i=1;i<=5;i++)
  100. {
  101.     if(dp[0][i])
  102.     {
  103.         list.add(i);
  104.         call(dp,list,ar,1);
  105.         break;
  106.     }
  107. }
  108. if(list.size()==0)
  109. {
  110.     s.append(-1);
  111. }
  112. else{
  113. for(int i:list)
  114. {
  115.     s.append(i+" ");
  116. }
  117. }
  118. pw.print(s);pw.close();}
  119. public static void call(boolean dp[][],ArrayList<Integer> list,int ar[],int i)
  120. {
  121.     if(i>=ar.length)
  122.     {
  123.         return;
  124.     }
  125. if(ar[i]>ar[i-1])
  126. {
  127.     for(int j=1;j<=5;j++)
  128.     {
  129.         if(dp[i][j] && j>list.get(list.size()-1))
  130.         {
  131.             list.add(j);
  132.             call(dp, list, ar, i+1);
  133.             break;
  134.         }
  135.     }
  136. }
  137. else if(ar[i]<ar[i-1])
  138. {
  139.     for(int j=1;j<=5;j++)
  140.     {
  141.         if(dp[i][j] && j<list.get(list.size()-1))
  142.         {
  143.             list.add(j);
  144.             call(dp, list, ar, i+1);
  145.             break;
  146.         }
  147.     }
  148. }
  149. else{
  150.     for(int j=1;j<=5;j++)
  151.     {
  152.         if(dp[i][j] && j!=list.get(list.size()-1))
  153.         {
  154.             list.add(j);
  155.             call(dp, list, ar, i+1);
  156.             break;
  157.         }
  158.     }
  159. }
  160. }
  161. }
  162.  
RAW Paste Data