# 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!
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) {
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}
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;
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;
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++) {
78.                 int r=l;
80.                 // to generate operation from {l, r}
81.                 func2(a, 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]
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) {
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.     }
238.         private InputStream stream;
239.         private byte[] buf = new byte[1024];
240.         private int curChar;
241.         private int numChars;
244.             this.stream = stream;
245.         }
246.
248.             if (numChars == -1) throw new InputMismatchException();
249.             if (curChar >= numChars) {
250.                 curChar = 0;
251.                 try {
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() {
263.             while (isSpaceChar(c)) c = read();
264.             int sgn = 1;
265.             if (c == '-') {
266.                 sgn = -1;
268.             }
269.             int res = 0;
270.             do {
271.                 if (c < '0' || c > '9') throw new InputMismatchException();
272.                 res *= 10;
273.                 res += c - '0';
275.             }
276.             while (!isSpaceChar(c));
277.             return res * sgn;
278.         }
279.
280.         public long nextLong() {
282.             while (isSpaceChar(c)) c = read();
283.             int sgn = 1;
284.             if (c == '-') {
285.                 sgn = -1;
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';
294.             }
295.             while (!isSpaceChar(c));
296.             return res *1L* sgn;
297.         }
298.
299.         public String next() {
301.             while (isSpaceChar(c)) c = read();
302.             StringBuilder res = new StringBuilder();
303.             do {
304.                 res.appendCodePoint(c);
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. }