| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 130698 | 2019-07-15T23:20:41 Z | MohamedAhmed04 | Brunhilda’s Birthday (BOI13_brunhilda) | C++14 | 1000 ms | 88464 KB |
#include <bits/stdc++.h>
using namespace std ;
const int MAX = 1e7 + 5 ;
const int OO = 1e9 ;
int dp[MAX] , freq[MAX] ;
int main()
{
int n , q ;
scanf("%d %d" , &n , &q) ;
int arr[n] ;
for(int i = 0 ; i < n ; ++i)
scanf("%d" , &arr[i]) ;
priority_queue< pair<int , int> , vector< pair<int , int> > , greater< pair<int , int> > >pq ;
priority_queue<int , vector<int> , greater<int> >pq2 ;
for(int i = 0 ; i < n ; ++i)
{
pq.push({arr[i] , arr[i]}) ;
pq2.push(0) ;
}
dp[0] = 0 ;
const int cons = 1e7 ;
for(int i = 1 ; i <= cons ; ++i)
{
while(pq.size() > 0)
{
pair<int , int>pp = pq.top() ;
if(pp.first == i)
{
pq.pop() ;
pq.push({pp.first + pp.second , pp.second}) ;
freq[pp.first - pp.second]++ ;
pq2.push(pp.first) ;
}
else
break ;
}
while(pq2.size() > 0)
{
int x = pq2.top() ;
if(freq[x])
{
pq2.pop() ;
freq[x]-- ;
}
else
break ;
}
int x = pq2.top();
if(x == i)
dp[i] = OO ;
else
dp[i] = dp[x] + 1 ;
}
while(q--)
{
int x ;
scanf("%d" , &x) ;
if(dp[x] >= OO)
cout<<"oo\n" ;
else
cout<<dp[x]<<"\n";
}
return 0 ;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 241 ms | 78652 KB | Output is correct |
| 2 | Execution timed out | 1080 ms | 58944 KB | Time limit exceeded |
| 3 | Correct | 740 ms | 78712 KB | Output is correct |
| 4 | Correct | 249 ms | 78716 KB | Output is correct |
| 5 | Correct | 444 ms | 78712 KB | Output is correct |
| 6 | Correct | 232 ms | 78588 KB | Output is correct |
| 7 | Correct | 740 ms | 78712 KB | Output is correct |
| 8 | Execution timed out | 1039 ms | 78712 KB | Time limit exceeded |
| 9 | Execution timed out | 1079 ms | 54520 KB | Time limit exceeded |
| 10 | Execution timed out | 1081 ms | 40172 KB | Time limit exceeded |
| 11 | Execution timed out | 1060 ms | 55412 KB | Time limit exceeded |
| 12 | Correct | 205 ms | 78588 KB | Output is correct |
| 13 | Execution timed out | 1080 ms | 16552 KB | Time limit exceeded |
| 14 | Execution timed out | 1077 ms | 16232 KB | Time limit exceeded |
| 15 | Execution timed out | 1084 ms | 59768 KB | Time limit exceeded |
| 16 | Execution timed out | 1075 ms | 59148 KB | Time limit exceeded |
| 17 | Correct | 566 ms | 78712 KB | Output is correct |
| 18 | Correct | 249 ms | 78732 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 633 ms | 79548 KB | Output is correct |
| 2 | Correct | 713 ms | 88464 KB | Output is correct |
| 3 | Execution timed out | 1079 ms | 46424 KB | Time limit exceeded |
| 4 | Execution timed out | 1093 ms | 63796 KB | Time limit exceeded |
| 5 | Execution timed out | 1068 ms | 32104 KB | Time limit exceeded |
| 6 | Execution timed out | 1090 ms | 55412 KB | Time limit exceeded |
| 7 | Correct | 631 ms | 79568 KB | Output is correct |
| 8 | Execution timed out | 1083 ms | 77360 KB | Time limit exceeded |
| 9 | Execution timed out | 1093 ms | 38104 KB | Time limit exceeded |
| 10 | Execution timed out | 1082 ms | 46540 KB | Time limit exceeded |
| 11 | Execution timed out | 1084 ms | 24892 KB | Time limit exceeded |
| 12 | Execution timed out | 1078 ms | 29368 KB | Time limit exceeded |
| 13 | Correct | 729 ms | 79368 KB | Output is correct |
| 14 | Execution timed out | 1086 ms | 62968 KB | Time limit exceeded |
| 15 | Execution timed out | 1087 ms | 24968 KB | Time limit exceeded |
| 16 | Correct | 709 ms | 88392 KB | Output is correct |
| 17 | Execution timed out | 1074 ms | 17000 KB | Time limit exceeded |
| 18 | Execution timed out | 1083 ms | 53456 KB | Time limit exceeded |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Execution timed out | 1085 ms | 25884 KB | Time limit exceeded |
| 2 | Execution timed out | 1087 ms | 22096 KB | Time limit exceeded |
| 3 | Execution timed out | 1086 ms | 25588 KB | Time limit exceeded |
| 4 | Execution timed out | 1081 ms | 27272 KB | Time limit exceeded |
| 5 | Correct | 899 ms | 84756 KB | Output is correct |
| 6 | Execution timed out | 1079 ms | 19020 KB | Time limit exceeded |
| 7 | Execution timed out | 1078 ms | 45916 KB | Time limit exceeded |
| 8 | Execution timed out | 1083 ms | 26252 KB | Time limit exceeded |
| 9 | Execution timed out | 1093 ms | 26940 KB | Time limit exceeded |
| 10 | Execution timed out | 1089 ms | 28528 KB | Time limit exceeded |
| 11 | Execution timed out | 1079 ms | 36812 KB | Time limit exceeded |
| 12 | Execution timed out | 1076 ms | 18920 KB | Time limit exceeded |
| 13 | Execution timed out | 1074 ms | 22876 KB | Time limit exceeded |
| 14 | Execution timed out | 1077 ms | 35700 KB | Time limit exceeded |
| 15 | Execution timed out | 1076 ms | 16552 KB | Time limit exceeded |
| 16 | Execution timed out | 1085 ms | 14972 KB | Time limit exceeded |
| 17 | Execution timed out | 1081 ms | 27596 KB | Time limit exceeded |
| 18 | Execution timed out | 1075 ms | 21736 KB | Time limit exceeded |
| 19 | Execution timed out | 1091 ms | 79244 KB | Time limit exceeded |
| 20 | Execution timed out | 1078 ms | 25480 KB | Time limit exceeded |
| 21 | Execution timed out | 1065 ms | 25316 KB | Time limit exceeded |
| 22 | Execution timed out | 1085 ms | 31628 KB | Time limit exceeded |
| 23 | Execution timed out | 1046 ms | 80888 KB | Time limit exceeded |
| 24 | Correct | 611 ms | 79308 KB | Output is correct |
| 25 | Execution timed out | 1080 ms | 25836 KB | Time limit exceeded |
| 26 | Execution timed out | 1084 ms | 27056 KB | Time limit exceeded |
| 27 | Execution timed out | 1085 ms | 46268 KB | Time limit exceeded |
| 28 | Correct | 920 ms | 79704 KB | Output is correct |
| 29 | Execution timed out | 1070 ms | 32472 KB | Time limit exceeded |
| 30 | Execution timed out | 1071 ms | 29932 KB | Time limit exceeded |
| 31 | Execution timed out | 1078 ms | 69212 KB | Time limit exceeded |
| 32 | Execution timed out | 1084 ms | 53608 KB | Time limit exceeded |
| 33 | Correct | 399 ms | 79224 KB | Output is correct |
| 34 | Execution timed out | 1080 ms | 46020 KB | Time limit exceeded |
| 35 | Execution timed out | 1076 ms | 79628 KB | Time limit exceeded |
| 36 | Execution timed out | 1092 ms | 31684 KB | Time limit exceeded |
| 37 | Correct | 890 ms | 84564 KB | Output is correct |
| 38 | Execution timed out | 1081 ms | 18912 KB | Time limit exceeded |
| 39 | Correct | 799 ms | 79244 KB | Output is correct |
| 40 | Execution timed out | 1086 ms | 23272 KB | Time limit exceeded |
| 41 | Execution timed out | 1088 ms | 64388 KB | Time limit exceeded |
| 42 | Execution timed out | 1072 ms | 15544 KB | Time limit exceeded |