| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 344408 |
2021-01-05T17:13:17 Z |
KWang31 |
Gift (IZhO18_nicegift) |
Java 11 |
|
285 ms |
54112 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(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+1+" ");
}
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+1+" ");
}
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((i+1)+" ");
}
}
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 |
Incorrect |
136 ms |
10844 KB |
Taken too much stones from the heap |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
136 ms |
10844 KB |
Taken too much stones from the heap |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
136 ms |
10844 KB |
Taken too much stones from the heap |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
285 ms |
54112 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
136 ms |
10844 KB |
Taken too much stones from the heap |
| 2 |
Halted |
0 ms |
0 KB |
- |
