source code clone download copy to clipboard report bug / make suggestion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <stdio.h>
int boxes[50005],a[50005],n,k;
 
void merge(int lower,int mid,int upper)
{
     int i=lower,j=mid+1,k=lower;
     while(i<=mid && j<=upper)
     {
                                 if(boxes[i]>=boxes[j])
                                     a[k++]=boxes[i++];
                                 else        
                                     a[k++]=boxes[j++]; 
     }
     while(i<=mid)
                  a[k++]=boxes[i++];
     while(j<=upper)
                    a[k++]=boxes[j++];
     for(i=lower;i<k;i++)
     {
                         boxes[i]=a[i];
     }
} 
 
int divide(int lower,int upper)
{
     int mid;
     mid = (lower + upper)/2;
     if(upper==lower)
                         return 0;
     divide(lower,mid);
     divide(mid+1,upper);
     merge(lower,mid,upper);
     return 1;
}
 
int bsearch(int lower,int upper)
{
     int mid = (lower+upper)/2,flag,p,j,u,max=0;
              
     for(;lower<=upper;mid=(lower+upper)/2)
     {
             flag=0;
             p=boxes[0]/mid;
             for(j=1;j<n;j++)
             {
                             
                             u=boxes[j]/mid;
                             if(u==0)
                                     break;
                             p+=u;
                             if(p>=k)
                             {
                                     flag=1;
                                     max=mid;
                                     break;
                             }
             }  
             if(flag)
                     lower=mid+1;
             else
                     upper=mid-1;
     }
     return max;
}
 
                    
 
int main()
{
    int t,i,maximum,s,count;
    scanf("%d%*c",&t);
    while(t--)
    {
              scanf("%d %d",&n,&k);
              for(i=0;i<n;i++)
                              scanf("%d",&boxes[i]);
              divide(0,n-1);
              if(boxes[0]==1)
              {
                             if(n<k)
                                    printf("0\n");
                             else
                             {
                                    for(i=0;i<n;i++)
                                                    if(boxes[i]==1)
                                                    count++;
                                    if(count>=k)
                                                printf("1\n");
                                    else
                                                printf("0\n");
                             }
              }
              else
              {
                             s=boxes[0]/k;
                             maximum=bsearch(s,boxes[0]);
                             if(s>maximum)
                                          maximum=s;
                             printf("%d\n",maximum);  
              } 
    }
    return 0;              
}
 

clone download copy to clipboard

• upload with new input
  You have reached a limit of free submissions this month.
  You cannot send submissions this month anymore because of exceeding your monthly limit. Please recharge your account.
  
• # 11:   hide show   clone   input   97 days 10 hours ago    Runtime error

  result: Runtime error     time: 0.02s    memory: 2108 kB     signal: 8 (SIGFPE)

  input:

  1
  2 4
  2 1

  output: no
• # 10:   hide show   clone   input   97 days 10 hours ago    Runtime error

  result: Runtime error     time: 0.01s    memory: 2108 kB     signal: 8 (SIGFPE)

  input:

  1
  2 4
  3 0

  output: no
• # 9:   hide show   clone   input   97 days 10 hours ago    Success

  result: Success     time: 0.01s    memory: 2112 kB     returned value: 0

  input:

  1
  2 7
  
  8 6

  output:

  2
  
• # 8:   hide show   clone   input   97 days 10 hours ago    Success

  result: Success     time: 0.01s    memory: 2112 kB     returned value: 0

  input:

  1
  1 7
  7

  output:

  1
  
• # 7:   hide show   clone   input   97 days 10 hours ago    Success

  result: Success     time: 0.01s    memory: 2112 kB     returned value: 0

  input:

  1
  1 7
  6

  output:

  0
  
• # 6:   hide show   clone   input   97 days 10 hours ago    Success

  result: Success     time: 0.01s    memory: 2112 kB     returned value: 0

  input:

  1
  1 1
  0

  output:

  0
  
• # 5:   hide show   clone   input   97 days 10 hours ago    Success

  result: Success     time: 0.02s    memory: 2112 kB     returned value: 0

  input:

  1
  2 2
  3 1921

  output:

  960
  
• # 4:   hide show   clone   input   97 days 10 hours ago    Success

  result: Success     time: 0.02s    memory: 2112 kB     returned value: 0

  input:

  1
  1 2
  2

  output:

  1
  
• # 3:   hide show   clone   input   97 days 10 hours ago    Success

  result: Success     time: 0.01s    memory: 2112 kB     returned value: 0

  input:

  3
  1 2
  2

  output:

  1
  1
  1
  
• # 2:   hide show   clone   input   97 days 13 hours ago    Success

  result: Success     time: 0.02s    memory: 2112 kB     returned value: 0

  input:

  1
  1 3
  18

  output:

  6
  
• # 1:   hide show   clone   input   97 days 16 hours ago    Success

  result: Success     time: 0.02s    memory: 2112 kB     returned value: 0

  input:

  2
  4 4 
  10 6 2 5
  4 1
  3 2 3 9

  output:

  5
  9