Submission #345710

#	Time	Username	Problem	Language	Result	Execution time	Memory
345710		KWang31	Gift (IZhO18_nicegift)	Java	49 / 100	2080 ms	151916 KiB

nicegift

import java.io.*; import java.util.*;
public class nicegift{
  static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
        long nextLong(){
            return Long.parseLong(next());
        }
        
    } 
    public static class Pair implements Comparable<Pair>{
        int ind; long val;
        public Pair(int a, long b){
            this.ind=a; this.val=b;
        }
        public int compareTo(Pair other){
            if(this.val<other.val)return -1;
            if(this.val>other.val)return 1;
            if(this.ind<other.ind)return -1;
            return 1;
        }
    }
    static int MOD=998244353;
    static int[] rk, p,siz;
    public static void main(String[] args){
        FastReader br=new FastReader();
        int N=br.nextInt(); int K=br.nextInt();
        Pair[] a=new Pair[N];
        long cur=0; 
        for (int i = 0; i < N; i++) {
            a[i]=new Pair(1+i,br.nextLong()); cur+=a[i].val; 
        }
        
        //A number is bottle neck if a[i]
        Arrays.sort(a);
        if(cur%K>0 || cur/K < a[N-1].val){
            System.out.println("-1");return;
        }
        cur/=K;
 
        //Tracks K+1 elements
        long d;
        long[] ans=new long[3000000]; int pt=0;
        int lp=0; int rp=N-1; 
        for (int j = 0; j < N; j++) {
        	
            while(lp<N && a[lp].val==0) {
        	lp++;
            }
            while(rp>=0 && a[rp].val==cur) {
                   rp--;
             }
            if(rp<lp)break;
            //System.out.println(j+" "+lp+" "+rp);
            d=Math.min(a[lp].val, cur-a[rp].val);
            if(d==0)continue;
            
            //System.out.println(j+" "+cur+" "+d);
            ans[pt++]=d; 
            //System.out.println(lp+K-(N-rp-1));
            for(int k=lp; k<lp+K-(N-rp-1); k++) {//There are at least K elements
            	a[k]=new Pair(a[k].ind,a[k].val-d); ans[pt++]=a[k].ind;
            	
            }
            for(int k=rp+1; k<N; k++) {
            	a[k]=new Pair(a[k].ind,a[k].val-d); ans[pt++]=a[k].ind;
            }
            cur-=d;
            
            
        }
        //Now K of them are "bottlenecks"
        
        boolean val=false;
        for (int i = 0; i < N; i++) {
            if(a[i].val>0){
            	
                if(!val){
                    val=true;
                    
                    ans[pt++]=a[i].val;
                }
                ans[pt++]=a[i].ind;
            }
        }
        System.out.println(pt/(K+1));
        StringBuilder sb=new StringBuilder();
        for (int i = 0; i < pt/(K+1); i++) {
            for (int j = 0; j <=K; j++) {
                sb.append(ans[i*(K+1)+j]+" ");
            }
            sb.append("\n");
            if(i*(K+1)%100000 < (i-1)*(K+1)%100000){
                System.out.println(sb.toString()); sb=new StringBuilder();
            }
        }
        System.out.println(sb.toString()); 
    }
    
    
}
//Debugging:
//Are you sure your algorithm is correct?
//Bounds: long
//Special cases: n=0,1?
//Make sure you remove your debugging code before you submit!

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 0 / 51