| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 344409 |
2021-01-05T17:15:26 Z |
KWang31 |
Gift (IZhO18_nicegift) |
Java 11 |
|
661 ms |
54052 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();
Pair[] a=new Pair[N];
long sum=0; long max=0;
for (int i = 0; i < N; i++) {
a[i]=new Pair(1+i,br.nextInt()); sum+=a[i].val; max=Math.max(max,a[i].val);
}
if(sum%K>0 || sum/K < max){
System.out.println("-1");return;
}
//A number is bottle neck if a[i]
Arrays.sort(a);
long cur=sum/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
v=a[k].val-d; a[k]=new Pair(a[k].ind,v); ans.append(a[k].ind+" ");
}
for(int k=rp+1; k<N; k++) {
v=a[k].val-d; a[k]=new Pair(a[k].ind,v); 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!
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
134 ms |
10584 KB |
n=4 |
| 2 |
Correct |
134 ms |
10656 KB |
n=3 |
| 3 |
Correct |
73 ms |
8544 KB |
n=3 |
| 4 |
Correct |
136 ms |
10596 KB |
n=4 |
| 5 |
Correct |
71 ms |
8556 KB |
n=4 |
| 6 |
Correct |
72 ms |
8428 KB |
n=2 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
134 ms |
10584 KB |
n=4 |
| 2 |
Correct |
134 ms |
10656 KB |
n=3 |
| 3 |
Correct |
73 ms |
8544 KB |
n=3 |
| 4 |
Correct |
136 ms |
10596 KB |
n=4 |
| 5 |
Correct |
71 ms |
8556 KB |
n=4 |
| 6 |
Correct |
72 ms |
8428 KB |
n=2 |
| 7 |
Correct |
138 ms |
10600 KB |
n=5 |
| 8 |
Correct |
74 ms |
8556 KB |
n=8 |
| 9 |
Correct |
137 ms |
10704 KB |
n=14 |
| 10 |
Correct |
134 ms |
10472 KB |
n=11 |
| 11 |
Correct |
661 ms |
21348 KB |
n=50000 |
| 12 |
Correct |
614 ms |
19532 KB |
n=50000 |
| 13 |
Correct |
135 ms |
10600 KB |
n=10 |
| 14 |
Correct |
165 ms |
10712 KB |
n=685 |
| 15 |
Correct |
170 ms |
10728 KB |
n=623 |
| 16 |
Correct |
200 ms |
11728 KB |
n=973 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
134 ms |
10584 KB |
n=4 |
| 2 |
Correct |
134 ms |
10656 KB |
n=3 |
| 3 |
Correct |
73 ms |
8544 KB |
n=3 |
| 4 |
Correct |
136 ms |
10596 KB |
n=4 |
| 5 |
Correct |
71 ms |
8556 KB |
n=4 |
| 6 |
Correct |
72 ms |
8428 KB |
n=2 |
| 7 |
Correct |
138 ms |
10600 KB |
n=5 |
| 8 |
Correct |
74 ms |
8556 KB |
n=8 |
| 9 |
Correct |
137 ms |
10704 KB |
n=14 |
| 10 |
Correct |
134 ms |
10472 KB |
n=11 |
| 11 |
Correct |
661 ms |
21348 KB |
n=50000 |
| 12 |
Correct |
614 ms |
19532 KB |
n=50000 |
| 13 |
Correct |
135 ms |
10600 KB |
n=10 |
| 14 |
Correct |
165 ms |
10712 KB |
n=685 |
| 15 |
Correct |
170 ms |
10728 KB |
n=623 |
| 16 |
Correct |
200 ms |
11728 KB |
n=973 |
| 17 |
Correct |
229 ms |
11900 KB |
n=989 |
| 18 |
Correct |
236 ms |
12028 KB |
n=563 |
| 19 |
Correct |
292 ms |
13152 KB |
n=592 |
| 20 |
Correct |
304 ms |
13152 KB |
n=938 |
| 21 |
Correct |
260 ms |
12256 KB |
n=747 |
| 22 |
Correct |
324 ms |
13376 KB |
n=991 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
280 ms |
54052 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
134 ms |
10584 KB |
n=4 |
| 2 |
Correct |
134 ms |
10656 KB |
n=3 |
| 3 |
Correct |
73 ms |
8544 KB |
n=3 |
| 4 |
Correct |
136 ms |
10596 KB |
n=4 |
| 5 |
Correct |
71 ms |
8556 KB |
n=4 |
| 6 |
Correct |
72 ms |
8428 KB |
n=2 |
| 7 |
Correct |
138 ms |
10600 KB |
n=5 |
| 8 |
Correct |
74 ms |
8556 KB |
n=8 |
| 9 |
Correct |
137 ms |
10704 KB |
n=14 |
| 10 |
Correct |
134 ms |
10472 KB |
n=11 |
| 11 |
Correct |
661 ms |
21348 KB |
n=50000 |
| 12 |
Correct |
614 ms |
19532 KB |
n=50000 |
| 13 |
Correct |
135 ms |
10600 KB |
n=10 |
| 14 |
Correct |
165 ms |
10712 KB |
n=685 |
| 15 |
Correct |
170 ms |
10728 KB |
n=623 |
| 16 |
Correct |
200 ms |
11728 KB |
n=973 |
| 17 |
Correct |
229 ms |
11900 KB |
n=989 |
| 18 |
Correct |
236 ms |
12028 KB |
n=563 |
| 19 |
Correct |
292 ms |
13152 KB |
n=592 |
| 20 |
Correct |
304 ms |
13152 KB |
n=938 |
| 21 |
Correct |
260 ms |
12256 KB |
n=747 |
| 22 |
Correct |
324 ms |
13376 KB |
n=991 |
| 23 |
Runtime error |
280 ms |
54052 KB |
Execution failed because the return code was nonzero |
| 24 |
Halted |
0 ms |
0 KB |
- |
