oj.uz

Submission #344041

# Submission time Handle Problem Language Result Execution time Memory
344041 2021-01-05T05:01:03 Z KWang31 Gift (IZhO18_nicegift) Java 11
7 / 100
 2000 ms 57900 KB 
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()); 
        } 
  
        
    } 
    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();
        long[] a=new long[N];
        long sum=0; long max=0;
        for (int i = 0; i < N; i++) {
            a[i]=br.nextInt(); sum+=a[i]; max=Math.max(max,a[i]);
        }
        if(sum%K>0 || sum/K < max){
            System.out.println("-1");return;
        }
        //A number is bottle neck if a[i]
        
        long cur=sum/K;
        
        
        PriorityQueue<Pair> pq=new PriorityQueue<>();
        //Tracks K+1 elements
        long d;StringBuilder ans=new StringBuilder();
        int op=0;
        for (int j = 0; j < N; j++) {
            pq=new PriorityQueue<>();
            for (int i = 0; i < N; i++) {
                if(pq.size()<=K){
                    pq.add(new Pair(i,a[i]));
                }else if(pq.peek().val < a[i]){
                    pq.poll(); pq.add(new Pair(i,a[i]));
                }
            }
            d=cur-pq.poll().val;
            if(d==0)continue;
            op++;
            d=Math.min(d,pq.peek().val);
            ans.append(d+" ");
            for (Pair p: pq) {
                ans.append((p.ind+1)+" ");
                a[p.ind]-=d;
            }
            ans.append("\n");
            cur-=d;
        }
        //Now K of them are "bottlenecks"
        
        boolean val=false;
        for (int i = 0; i < N; i++) {
            if(a[i]>0){
                if(!val){
                    val=true;
                    op++;
                    ans.append(a[i]+" ");
                }
                ans.append((i+1)+" ");
            }
        }
        System.out.println(op);
        System.out.println(ans.toString());
    }
    
    public static int find(int x, int[] p){
        if(p[x]==x)return x;
        int ans=find(p[x],p); p[x]=ans; return ans;
    }
    
    public static void merge(int a, int b) {
        if(rk[a]<rk[b]) {
            p[a]=b; siz[b]+=siz[a];
        }else if(rk[a]==rk[b]) {
            p[a]=b; rk[b]++;siz[b]+=siz[a];
        }else {
            p[b]=a; siz[a]+=siz[b];
        }
    }
    public static long pow(int b, int e){
        if(e==0)return 1; if(e==1)return b;
        long x=pow(b,e/2); x*=x; x%=MOD; x*=pow(b,e%2); return x%MOD;
    }
  public static void dfs(ArrayList<Integer>[] arl, int cur){
       
        for (int i : arl[cur]) {
            
            
            
        }
        
    }
}
//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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 10568 KB n=4
2 Correct 142 ms 10700 KB n=3
3 Correct 74 ms 8580 KB n=3
4 Correct 140 ms 10520 KB n=4
5 Correct 74 ms 8556 KB n=4
6 Correct 72 ms 8540 KB n=2

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 10568 KB n=4
2 Correct 142 ms 10700 KB n=3
3 Correct 74 ms 8580 KB n=3
4 Correct 140 ms 10520 KB n=4
5 Correct 74 ms 8556 KB n=4
6 Correct 72 ms 8540 KB n=2
7 Correct 139 ms 10584 KB n=5
8 Correct 72 ms 8684 KB n=8
9 Correct 139 ms 10832 KB n=14
10 Correct 139 ms 10464 KB n=11
11 Execution timed out 2076 ms 16400 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 10568 KB n=4
2 Correct 142 ms 10700 KB n=3
3 Correct 74 ms 8580 KB n=3
4 Correct 140 ms 10520 KB n=4
5 Correct 74 ms 8556 KB n=4
6 Correct 72 ms 8540 KB n=2
7 Correct 139 ms 10584 KB n=5
8 Correct 72 ms 8684 KB n=8
9 Correct 139 ms 10832 KB n=14
10 Correct 139 ms 10464 KB n=11
11 Execution timed out 2076 ms 16400 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 264 ms 57900 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #5
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 10568 KB n=4
2 Correct 142 ms 10700 KB n=3
3 Correct 74 ms 8580 KB n=3
4 Correct 140 ms 10520 KB n=4
5 Correct 74 ms 8556 KB n=4
6 Correct 72 ms 8540 KB n=2
7 Correct 139 ms 10584 KB n=5
8 Correct 72 ms 8684 KB n=8
9 Correct 139 ms 10832 KB n=14
10 Correct 139 ms 10464 KB n=11
11 Execution timed out 2076 ms 16400 KB Time limit exceeded
12 Halted 0 ms 0 KB -