Guest User

Untitled

a guest
Jan 19th, 2021
472
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 4.80 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.*;
  3. public class C{
  4.     // static PrintWriter out=new PrintWriter(System.out);
  5.     static BufferedWriter out=new BufferedWriter(new OutputStreamWriter(System.out));
  6.     static FastReader in=new FastReader();
  7.     static int MAX=(int)1e6+10;
  8.     public static void main(String[] args) throws IOException{
  9.         int T;
  10.         T=in.nextInt();
  11. //      T=1;
  12.         for(int t=1; t<=T; ++t) solve(t);
  13.         out.flush();
  14.         out.close();
  15.     }
  16.     static void decByOne(TreeMap<Integer, Integer> freq, int key){
  17.         freq.put(key, freq.get(key)-1);
  18.         if(freq.get(key)==0) freq.remove(key);
  19.     }
  20.     static void incByOne(TreeMap<Integer, Integer> freq, int key){
  21.         freq.put(key, freq.getOrDefault(key, 0)+1);
  22.     }
  23.     static boolean possible(TreeMap<Integer, Integer> freq, int sum, boolean printSol) throws IOException {
  24.         if(freq.size()==0) return true;
  25.         int last=freq.lastKey();
  26.         decByOne(freq, last);
  27.         int required=sum-last;
  28.         boolean isPossible;
  29.         if(!freq.containsKey(required)){
  30.             isPossible=false;
  31.         }
  32.         else{
  33.             decByOne(freq, required);
  34.             if(printSol) out.write(last+" "+required+"\n");
  35.             isPossible=possible(freq, last, printSol);
  36.             incByOne(freq, required);
  37.         }
  38.         incByOne(freq, last);
  39.         return isPossible;
  40.     }
  41.     static void solve(int testCase) throws IOException{
  42.         // out.print("Case #"+testCase+": ");
  43.         TreeMap<Integer, Integer> freq=new TreeMap<>();
  44.         int n=in.nextInt();
  45.         int[] arr=new int[2*n];
  46.         for(int i=0; i<2*n; ++i){
  47.             arr[i]=in.nextInt();
  48.             freq.put(arr[i], freq.getOrDefault(arr[i], 0)+1);
  49.         }
  50.         Utility.fastSort(arr);
  51.         int last=arr[2*n-1];
  52.         // Utility.debug(last);
  53.         decByOne(freq, last);
  54.         for(int j=2*n-2; j>=0; --j){
  55.             int ele=arr[j];
  56.             decByOne(freq, ele);
  57.             int sum=last+ele;
  58.             // Utility.debug("Sum is", sum);
  59.             // out.println(freq.toString());
  60.             if(possible(freq, last, false)){
  61.                 out.write("YES\n");
  62.                 out.write(sum+"\n");
  63.                 out.write(last+" "+ele+"\n");
  64.                 possible(freq, last, true);
  65.                 return;
  66.             } else{
  67.                 incByOne(freq, ele);
  68.             }
  69.         }
  70.         out.write("NO\n");
  71.  
  72.     }
  73.     static class Utility{
  74.         static final String sep="#".repeat(10);
  75.         static int gcd(int a, int b){
  76.             if(b==0) return a;
  77.             return gcd(b, a%b);
  78.         }
  79.         static long gcd(long a, long b){
  80.             if(b==0) return a;
  81.             return gcd(b, a%b);
  82.         }
  83.         static void fastSort(int[] arr){
  84.             ArrayList<Integer> a=new ArrayList<>();
  85.             for(int x: arr) a.add(x);
  86.             Collections.sort(a);
  87.             for(int i=0; i<a.size(); ++i) arr[i]=a.get(i);
  88.         }
  89.         static void fastSort(long[] arr){
  90.             ArrayList<Long> a=new ArrayList<>();
  91.             for(long x: arr) a.add(x);
  92.             Collections.sort(a);
  93.             for(int i=0; i<a.size(); ++i) arr[i]=a.get(i);
  94.         }
  95.         // static void debug(int[] arr){
  96.         //     out.println(sep);
  97.         //     out.println("[DEBUG] " + Arrays.toString(arr));
  98.         //     out.println(sep);
  99.         // }
  100.         // static void debug(long[] arr){
  101.         //     out.println(sep);
  102.         //     out.println("[DEBUG] " + Arrays.toString(arr));
  103.         //     out.println(sep);
  104.         // }
  105.         // static void debug(Object... args){
  106.         //     out.println(sep); out.print("[DEBUG] ");
  107.         //     for(Object o: args) out.print(o + " ");
  108.         //     out.println(); out.println(sep);
  109.         // }
  110.     }
  111.     static class FastReader{
  112.         BufferedReader br;
  113.         StringTokenizer st;
  114.         public FastReader(){
  115.             br=new BufferedReader(new InputStreamReader(System.in));
  116.         }
  117.         String next(){
  118.             while(st==null||!st.hasMoreElements()){
  119.                 try{
  120.                     st=new StringTokenizer(br.readLine());
  121.                 }catch(IOException e){
  122.                     e.printStackTrace();
  123.                 }
  124.             }
  125.             return st.nextToken();
  126.         }
  127.         int nextInt(){
  128.             return Integer.parseInt(next());
  129.         }
  130.         long nextLong(){
  131.             return Long.parseLong(next());
  132.         }
  133.         double nextDouble(){
  134.             return Double.parseDouble(next());
  135.         }
  136.         String nextLine(){
  137.             String str="";
  138.             try{
  139.                 str=br.readLine();
  140.             }catch(IOException e){
  141.                 e.printStackTrace();
  142.             }
  143.             return str;
  144.         }
  145.     }
  146. }
  147.  
Advertisement
Add Comment
Please, Sign In to add comment