| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 345712 |
2021-01-08T01:00:46 Z |
KWang31 |
Gift (IZhO18_nicegift) |
Java 11 |
|
2000 ms |
133144 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;
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]+" ");
}
System.out.println(sb.toString()); sb=new StringBuilder();
}
}
}
//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 |
33636 KB |
n=4 |
| 2 |
Correct |
140 ms |
33860 KB |
n=3 |
| 3 |
Correct |
75 ms |
8440 KB |
n=3 |
| 4 |
Correct |
135 ms |
33844 KB |
n=4 |
| 5 |
Correct |
77 ms |
8420 KB |
n=4 |
| 6 |
Correct |
75 ms |
8712 KB |
n=2 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
134 ms |
33636 KB |
n=4 |
| 2 |
Correct |
140 ms |
33860 KB |
n=3 |
| 3 |
Correct |
75 ms |
8440 KB |
n=3 |
| 4 |
Correct |
135 ms |
33844 KB |
n=4 |
| 5 |
Correct |
77 ms |
8420 KB |
n=4 |
| 6 |
Correct |
75 ms |
8712 KB |
n=2 |
| 7 |
Correct |
135 ms |
33700 KB |
n=5 |
| 8 |
Correct |
75 ms |
8548 KB |
n=8 |
| 9 |
Correct |
136 ms |
33872 KB |
n=14 |
| 10 |
Correct |
144 ms |
33824 KB |
n=11 |
| 11 |
Correct |
1047 ms |
42204 KB |
n=50000 |
| 12 |
Correct |
1022 ms |
42352 KB |
n=50000 |
| 13 |
Correct |
137 ms |
33872 KB |
n=10 |
| 14 |
Correct |
208 ms |
34284 KB |
n=685 |
| 15 |
Correct |
212 ms |
34004 KB |
n=623 |
| 16 |
Correct |
244 ms |
34700 KB |
n=973 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
134 ms |
33636 KB |
n=4 |
| 2 |
Correct |
140 ms |
33860 KB |
n=3 |
| 3 |
Correct |
75 ms |
8440 KB |
n=3 |
| 4 |
Correct |
135 ms |
33844 KB |
n=4 |
| 5 |
Correct |
77 ms |
8420 KB |
n=4 |
| 6 |
Correct |
75 ms |
8712 KB |
n=2 |
| 7 |
Correct |
135 ms |
33700 KB |
n=5 |
| 8 |
Correct |
75 ms |
8548 KB |
n=8 |
| 9 |
Correct |
136 ms |
33872 KB |
n=14 |
| 10 |
Correct |
144 ms |
33824 KB |
n=11 |
| 11 |
Correct |
1047 ms |
42204 KB |
n=50000 |
| 12 |
Correct |
1022 ms |
42352 KB |
n=50000 |
| 13 |
Correct |
137 ms |
33872 KB |
n=10 |
| 14 |
Correct |
208 ms |
34284 KB |
n=685 |
| 15 |
Correct |
212 ms |
34004 KB |
n=623 |
| 16 |
Correct |
244 ms |
34700 KB |
n=973 |
| 17 |
Correct |
250 ms |
35000 KB |
n=989 |
| 18 |
Correct |
248 ms |
34912 KB |
n=563 |
| 19 |
Correct |
286 ms |
35336 KB |
n=592 |
| 20 |
Correct |
387 ms |
35432 KB |
n=938 |
| 21 |
Correct |
272 ms |
35408 KB |
n=747 |
| 22 |
Correct |
387 ms |
36656 KB |
n=991 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2051 ms |
133144 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
134 ms |
33636 KB |
n=4 |
| 2 |
Correct |
140 ms |
33860 KB |
n=3 |
| 3 |
Correct |
75 ms |
8440 KB |
n=3 |
| 4 |
Correct |
135 ms |
33844 KB |
n=4 |
| 5 |
Correct |
77 ms |
8420 KB |
n=4 |
| 6 |
Correct |
75 ms |
8712 KB |
n=2 |
| 7 |
Correct |
135 ms |
33700 KB |
n=5 |
| 8 |
Correct |
75 ms |
8548 KB |
n=8 |
| 9 |
Correct |
136 ms |
33872 KB |
n=14 |
| 10 |
Correct |
144 ms |
33824 KB |
n=11 |
| 11 |
Correct |
1047 ms |
42204 KB |
n=50000 |
| 12 |
Correct |
1022 ms |
42352 KB |
n=50000 |
| 13 |
Correct |
137 ms |
33872 KB |
n=10 |
| 14 |
Correct |
208 ms |
34284 KB |
n=685 |
| 15 |
Correct |
212 ms |
34004 KB |
n=623 |
| 16 |
Correct |
244 ms |
34700 KB |
n=973 |
| 17 |
Correct |
250 ms |
35000 KB |
n=989 |
| 18 |
Correct |
248 ms |
34912 KB |
n=563 |
| 19 |
Correct |
286 ms |
35336 KB |
n=592 |
| 20 |
Correct |
387 ms |
35432 KB |
n=938 |
| 21 |
Correct |
272 ms |
35408 KB |
n=747 |
| 22 |
Correct |
387 ms |
36656 KB |
n=991 |
| 23 |
Execution timed out |
2051 ms |
133144 KB |
Time limit exceeded |
| 24 |
Halted |
0 ms |
0 KB |
- |
