Advertisement
coder0687

CF 939 D. Nene and the Mex Operator

Apr 16th, 2024 (edited)
562
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 9.23 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.*;
  3. import static java.lang.System.*;
  4. import static java.lang.Math.*;
  5. // reference taken from editorial and solution from : https://www.youtube.com/watch?v=lrX0a-kjIk8
  6. public class D {
  7.     List<int[]> op;
  8.     void run() {
  9.         int tc=ni();
  10.         while(tc-->0) {
  11.             int n=ni(), a[]=ni(n);
  12.             op = new ArrayList<>();
  13.             func(a);
  14.             int s = 0;
  15.             for(int v: a) s += v;
  16.             ap(s(s), " ", s(op.size()), "\n");
  17.             for(int indx[]: op) {
  18.                 for(int i: indx) ap(s(i+1), " ");
  19.                 ap("\n");
  20.             }
  21.             ap("\n");
  22.         }
  23.         out.println(sb);
  24.         out.flush();
  25.         out.close();
  26.     }
  27.     // in this we will create a sequence of 0, 1, 2, . . .
  28.     void func2(int a[], int l, int r) {
  29.         if(l == r) {
  30.             if(a[l] != 0) {
  31.                 op.add(new int[]{l, l});
  32.                 a[l] = 0;
  33.             }
  34.             return;
  35.         }
  36.         // set all the elements to zero; we have to check individually each of them
  37.         // bcz it might happen that already it contains 0
  38.         func2(a, l+1, r);
  39.         // check if its having a sequence of [r-l, r-l-1, . . . 1, 0] b/w {l, r},
  40.         if(a[l] != r-l) {
  41.             // if not then we have to set r-l to all bcz we have already [r-l-1, . . 1, 0] b/w {l+1, r}
  42.             op.add(new int[]{l, r});
  43.             for(int i = l; i <= r; i++) {
  44.                 a[i] = r - l;
  45.             }
  46.             // and here we call again {l+1, r} to create a sequence of [r-l-1, . . . 1, 0] b/w {l+1, r}
  47.             func2(a, l + 1, r);
  48.         }
  49.     }
  50.     void func(int a[]) {
  51.         int n = a.length;
  52.         int bstMask=0, bstSum=0;
  53.         for(int i = 0; i < (1<<n); i++) {
  54.             int tmp = 0;
  55.             for(int l=0;l<n;l++) {
  56.                 // if 0 at ith bit means we have to replace all with length
  57.                 if((i&(1<<l)) == 0) {
  58.                     int r = l;
  59.                     while(r+1<n && (i&(1<<(r+1)))==0) ++r;
  60.                     tmp += (r-l+1) * (r-l+1);
  61.                     l=r;
  62.                 }
  63.                 else {
  64.                     tmp += a[l];
  65.                 }
  66.             }
  67.             if(bstSum < tmp) {
  68.                 bstSum = tmp;
  69.                 bstMask = i;
  70.             }
  71.         }
  72.        
  73.         // debug(Integer.toBinaryString(bstMask), " ", s(bstSum));
  74.  
  75.         // now here we will generate all the operation needed to get bstSum from bstMask
  76.         for(int l=0;l<n;l++) {
  77.             if((bstMask&(1<<l)) == 0) {
  78.                 int r=l;
  79.                 while(r+1<n && (bstMask&(1<<(r+1)))==0) ++r;
  80.                 // to generate operation from {l, r}
  81.                 func2(a, l, r);
  82.                 op.add(new int[]{l, r});
  83.  
  84.                 for(int i=l;i<=r;i++) {
  85.                     a[i] = r-l+1;
  86.                 }
  87.                 l=r;
  88.             }
  89.         }
  90.     }
  91.     void funcX(int a[], int l, int r) {
  92.         if(l > r) return;
  93.         int s = 0;
  94.         for(int i=l;i<=r;i++) s += a[i];
  95.         // if sum of all elements b/w {l, r} is less than square of length
  96.         // then try to create a sequence of 0, 1, 2, . . . to get max value
  97.         if(s < (r - l + 1) * (r - l + 1)) {
  98.             func2(a, l, r);
  99.             // now after func2 it becomes like [r-l, r-l-1, . . . 1, 0]
  100.             op.add(new int[]{l, r});
  101.             // so after applying operation {l, r} all a[i] becomes (r - l + 1);
  102.             for(int i=l;i<=r;i++) {
  103.                 a[i] = r - l + 1;
  104.             }
  105.         }
  106.         // else here we will split based on the max position of element in array and do same thing recursively
  107.         else {
  108.             int mx = -1, pos = -1;
  109.             for(int i=l;i<=r;i++) {
  110.                 if(mx < a[i]) {
  111.                     mx = a[i];
  112.                     pos = i;
  113.                 }
  114.             }
  115.             funcX(a, l, pos-1);
  116.             funcX(a, pos+1, r);
  117.         }
  118.     }
  119.     public static void main(String[] args)throws Exception {
  120.         try {
  121.             new Thread(null, new D()::run, "1", 1 << 26).start();
  122.             // new Thread(null, new D("ONLINE_JUDGE")::run, "1", 1 << 26).start();
  123.         } catch(Exception e) {}
  124.     }
  125.  
  126.     FastReader sc=null;PrintWriter out = null;
  127.     public D()throws Exception {
  128.         sc = new FastReader(new FileInputStream("../input.txt"));
  129.         out = new PrintWriter(new BufferedWriter(new FileWriter("../output.txt")));
  130.     }
  131.     public D(String JUDGE) {
  132.         sc = new FastReader(System.in);
  133.         out = new PrintWriter(System.out);      
  134.     }
  135.  
  136.     long ceil(long a, long b) {
  137.         return (a + b - 1) / b;
  138.     }
  139.  
  140.     StringBuilder sb = new StringBuilder();
  141.     final int IMAX = Integer.MAX_VALUE;
  142.     final int IMIN = Integer.MIN_VALUE;
  143.     final long LMAX = Long.MAX_VALUE;
  144.     final long LMIN = Long.MIN_VALUE;
  145.     final int MOD = (int)1e9+7;
  146.  
  147.     void ap(String... str) {
  148.         for(String s: str) sb.append(s);
  149.     }
  150.     void ap(Integer... arr) {
  151.         for(Integer a: arr) sb.append(a);
  152.     }
  153.     void ap(Long... arr) {
  154.         for(Long a: arr) sb.append(a);
  155.     }
  156.     void debug(String... str) {
  157.         for(String s: str) System.out.print(s+" - ");
  158.         System.out.println();
  159.     }
  160.     void debug(Integer... a) {
  161.         for(Integer v: a) System.out.print(v+" - ");
  162.         System.out.println();
  163.     }
  164.     void debug(Long... a) {
  165.         for(long v: a) System.out.print(v+" - ");
  166.         System.out.println();
  167.     }
  168.     void debug(int a[], Integer... b) {
  169.         System.out.println(Arrays.toString(a));
  170.         debug(b);
  171.     }
  172.     void debug(int a[][], Integer... b) {
  173.         System.out.println(Arrays.deepToString(a));
  174.         debug(b);
  175.     }
  176.     void debug(long a[], Long... b) {
  177.         System.out.println(Arrays.toString(a));
  178.         debug(b);
  179.     }
  180.     void debug(long a[][], Long... b) {
  181.         System.out.println(Arrays.deepToString(a));
  182.         debug(b);
  183.     }
  184.     String s(Long n) {
  185.         return String.valueOf(n);
  186.     }
  187.     String s(Integer n) {
  188.         return String.valueOf(n);
  189.     }
  190.  
  191.     String ns() { return sc.next(); }
  192.     int ni() { return sc.nextInt(); }
  193.     long nl() { return sc.nextLong(); }
  194.     char[] nc() {
  195.         return ns().toCharArray();
  196.     }
  197.     char[][] nc(int n) {
  198.         char c[][] = new char[n][];
  199.         for(int i=0;i<n;i++) {
  200.             c[i] = ns().toCharArray();
  201.         }
  202.         return c;
  203.     }
  204.     int[][] _ni(int n) {
  205.         int a[][] = new int[n][];
  206.         for(int i=0;i<n;a[i]=new int[]{i, ni()});
  207.         return a;
  208.     }
  209.     int[] ni(int n) {
  210.         int a[]=new int[n];
  211.         for(int i=0;i<n;a[i++]=ni());
  212.         return a;
  213.     }
  214.     long[] nl(int n) {
  215.         long a[]=new long[n];
  216.         for(int i=0;i<n;a[i++]=nl());
  217.         return a;
  218.     }
  219.    
  220.     int[][] ni(int n,int m) {
  221.         int a[][]=new int[n][m];
  222.         for(int i=0;i<n;i++)
  223.             for(int j=0;j<m;j++)
  224.                 a[i][j]=ni();
  225.         return a;
  226.     }
  227.     long[][] nl(int n,int m) {
  228.         long a[][]=new long[n][m];
  229.         for(int i=0;i<n;i++)
  230.             for(int j=0;j<m;j++)
  231.                 a[i][j]=nl();
  232.         return a;
  233.     }
  234.     int gcd(int a, int b) {
  235.         return b==0?a:gcd(b,a%b);
  236.     }
  237.     static class FastReader {
  238.         private InputStream stream;
  239.         private byte[] buf = new byte[1024];
  240.         private int curChar;
  241.         private int numChars;
  242.         private FastReader.SpaceCharFilter filter;
  243.         public FastReader(InputStream stream) {
  244.             this.stream = stream;
  245.         }
  246.  
  247.         public int read() {
  248.             if (numChars == -1) throw new InputMismatchException();
  249.             if (curChar >= numChars) {
  250.                 curChar = 0;
  251.                 try {
  252.                     numChars = stream.read(buf);
  253.                 } catch (IOException e) {
  254.                     throw new InputMismatchException();
  255.                 }
  256.                 if (numChars <= 0) return -1;
  257.             }
  258.             return buf[curChar++];
  259.         }
  260.  
  261.         public int nextInt() {
  262.             int c = read();
  263.             while (isSpaceChar(c)) c = read();
  264.             int sgn = 1;
  265.             if (c == '-') {
  266.                 sgn = -1;
  267.                 c = read();
  268.             }
  269.             int res = 0;
  270.             do {
  271.                 if (c < '0' || c > '9') throw new InputMismatchException();
  272.                 res *= 10;
  273.                 res += c - '0';
  274.                 c = read();
  275.             }
  276.             while (!isSpaceChar(c));
  277.             return res * sgn;
  278.         }
  279.        
  280.         public long nextLong() {
  281.             int c = read();
  282.             while (isSpaceChar(c)) c = read();
  283.             int sgn = 1;
  284.             if (c == '-') {
  285.                 sgn = -1;
  286.                 c = read();
  287.             }
  288.             long res = 0;
  289.             do {
  290.                 if (c < '0' || c > '9') throw new InputMismatchException();
  291.                 res = res*1L*10;
  292.                 res += c - '0';
  293.                 c = read();
  294.             }
  295.             while (!isSpaceChar(c));
  296.             return res *1L* sgn;
  297.         }
  298.        
  299.         public String next() {
  300.             int c = read();
  301.             while (isSpaceChar(c)) c = read();
  302.             StringBuilder res = new StringBuilder();
  303.             do {
  304.                 res.appendCodePoint(c);
  305.                 c = read();
  306.             } while (!isSpaceChar(c));
  307.             return res.toString();
  308.         }
  309.  
  310.         public boolean isSpaceChar(int c) {
  311.             if (filter != null) return filter.isSpaceChar(c);
  312.             return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  313.         }
  314.  
  315.         public interface SpaceCharFilter {
  316.             public boolean isSpaceChar(int ch);
  317.  
  318.         }
  319.     }
  320. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement