oj.uz

답안 #345706

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
345706 2021-01-08T00:49:18 Z KWang31 Gift (IZhO18_nicegift) Java 11
49 / 100
 2000 ms 158320 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()); 
        } 
        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;StringBuilder ans=new StringBuilder();
        int op=0; int lp=0; int rp=N-1; long v; 
        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;
            op++;
            //System.out.println(j+" "+cur+" "+d);
            ans.append(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.append(a[k].ind+" ");
            	
            }
            for(int k=rp+1; k<N; k++) {
            	a[k]=new Pair(a[k].ind,a[k].val-d); ans.append(a[k].ind+" ");
            }
            cur-=d;
            ans.append("\n"); 
            
        }
        //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;
                    op++;
                    ans.append(a[i].val+" ");
                }
                ans.append(a[i].ind+" ");
            }
        }
        System.out.println(op);
        System.out.println(ans.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.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 135 ms 10472 KB n=4
2 Correct 137 ms 10504 KB n=3
3 Correct 72 ms 8460 KB n=3
4 Correct 140 ms 10352 KB n=4
5 Correct 73 ms 8556 KB n=4
6 Correct 80 ms 8428 KB n=2

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 135 ms 10472 KB n=4
2 Correct 137 ms 10504 KB n=3
3 Correct 72 ms 8460 KB n=3
4 Correct 140 ms 10352 KB n=4
5 Correct 73 ms 8556 KB n=4
6 Correct 80 ms 8428 KB n=2
7 Correct 141 ms 10492 KB n=5
8 Correct 73 ms 8528 KB n=8
9 Correct 150 ms 10692 KB n=14
10 Correct 141 ms 10600 KB n=11
11 Correct 660 ms 20952 KB n=50000
12 Correct 632 ms 19468 KB n=50000
13 Correct 135 ms 10620 KB n=10
14 Correct 164 ms 10876 KB n=685
15 Correct 170 ms 10656 KB n=623
16 Correct 199 ms 11528 KB n=973

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 135 ms 10472 KB n=4
2 Correct 137 ms 10504 KB n=3
3 Correct 72 ms 8460 KB n=3
4 Correct 140 ms 10352 KB n=4
5 Correct 73 ms 8556 KB n=4
6 Correct 80 ms 8428 KB n=2
7 Correct 141 ms 10492 KB n=5
8 Correct 73 ms 8528 KB n=8
9 Correct 150 ms 10692 KB n=14
10 Correct 141 ms 10600 KB n=11
11 Correct 660 ms 20952 KB n=50000
12 Correct 632 ms 19468 KB n=50000
13 Correct 135 ms 10620 KB n=10
14 Correct 164 ms 10876 KB n=685
15 Correct 170 ms 10656 KB n=623
16 Correct 199 ms 11528 KB n=973
17 Correct 230 ms 11900 KB n=989
18 Correct 241 ms 11928 KB n=563
19 Correct 290 ms 13152 KB n=592
20 Correct 310 ms 12980 KB n=938
21 Correct 255 ms 12020 KB n=747
22 Correct 321 ms 13248 KB n=991

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1291 ms 132588 KB n=1000000
2 Correct 999 ms 80932 KB n=666666
3 Correct 798 ms 51936 KB n=400000
4 Correct 811 ms 46536 KB n=285714
5 Correct 562 ms 16804 KB n=20000
6 Correct 682 ms 31860 KB n=181818
7 Correct 490 ms 15732 KB n=10000
8 Correct 417 ms 15200 KB n=6666
9 Correct 334 ms 15068 KB n=4000
10 Correct 426 ms 15284 KB n=2857
11 Correct 267 ms 13536 KB n=2000

Subtask #5
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 135 ms 10472 KB n=4
2 Correct 137 ms 10504 KB n=3
3 Correct 72 ms 8460 KB n=3
4 Correct 140 ms 10352 KB n=4
5 Correct 73 ms 8556 KB n=4
6 Correct 80 ms 8428 KB n=2
7 Correct 141 ms 10492 KB n=5
8 Correct 73 ms 8528 KB n=8
9 Correct 150 ms 10692 KB n=14
10 Correct 141 ms 10600 KB n=11
11 Correct 660 ms 20952 KB n=50000
12 Correct 632 ms 19468 KB n=50000
13 Correct 135 ms 10620 KB n=10
14 Correct 164 ms 10876 KB n=685
15 Correct 170 ms 10656 KB n=623
16 Correct 199 ms 11528 KB n=973
17 Correct 230 ms 11900 KB n=989
18 Correct 241 ms 11928 KB n=563
19 Correct 290 ms 13152 KB n=592
20 Correct 310 ms 12980 KB n=938
21 Correct 255 ms 12020 KB n=747
22 Correct 321 ms 13248 KB n=991
23 Correct 1291 ms 132588 KB n=1000000
24 Correct 999 ms 80932 KB n=666666
25 Correct 798 ms 51936 KB n=400000
26 Correct 811 ms 46536 KB n=285714
27 Correct 562 ms 16804 KB n=20000
28 Correct 682 ms 31860 KB n=181818
29 Correct 490 ms 15732 KB n=10000
30 Correct 417 ms 15200 KB n=6666
31 Correct 334 ms 15068 KB n=4000
32 Correct 426 ms 15284 KB n=2857
33 Correct 267 ms 13536 KB n=2000
34 Correct 1055 ms 18812 KB n=23514
35 Correct 1177 ms 18704 KB n=23514
36 Correct 157 ms 10856 KB n=940
37 Correct 133 ms 10600 KB n=2
38 Correct 1669 ms 32928 KB n=100000
39 Correct 1507 ms 32444 KB n=100000
40 Correct 144 ms 10712 KB n=10
41 Correct 224 ms 11900 KB n=100
42 Correct 435 ms 17440 KB n=1000
43 Correct 1466 ms 158320 KB n=1000000
44 Execution timed out 2053 ms 78148 KB Time limit exceeded
45 Halted 0 ms 0 KB -