| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 243615 |
2020-07-01T12:16:22 Z |
uacoder123 |
Gap (APIO16_gap) |
C++14 |
|
82 ms |
3480 KB |
#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))
typedef long long int lli;
typedef pair <lli,lli> ii;
typedef pair <lli,ii> iii;
typedef vector <lli> vi;
long long findGap(int T, int N)
{
lli c=0,arr[N],l=0,rem=0,g,r=1000000000000000000,l1=0,r1=N-1,ans1,ans2,m=0;
if(T==1)
{
for(;l1<=r1;)
{
MinMax(l,r,&ans1,&ans2);
arr[l1]=ans1;
l1++;
l=ans1+1;
arr[r1]=ans2;
r1--;
r=ans2-1;
}
for(lli i=0;i<N-1;++i)
m=max(m,arr[i+1]-arr[i]);
}
else
{
MinMax(l,r,&ans1,&ans2);
l=ans1+1;
r=ans2-1;
g=(r-l+1)/(N-1);
rem+=(r-l+1)%(N-1);
r1=g+l-1;
vector<ii> v;
v.pb(mp(ans1,ans1));
while(1)
{
MinMax(l,min(r1+min(1*1LL,rem),r),&ans1,&ans2);
if(ans1!=-1)
v.pb(mp(ans1,ans2));
if(r<=r1+min(1*1LL,rem))
break;
l=1+r1+min(1*1LL,rem);
r1=r1+min(1*1LL,rem)+g;
if(rem>0)
rem-=1;
}
v.pb(mp(r+1,r+1));
for(lli i=0;i<lli(v.size())-1;++i)
{
m=max(m,v[i+1].F-v[i].S);
}
}
return m;
}
Compilation message
gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:21:7: warning: unused variable 'c' [-Wunused-variable]
lli c=0,arr[N],l=0,rem=0,g,r=1000000000000000000,l1=0,r1=N-1,ans1,ans2,m=0;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
416 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
4 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
4 ms |
384 KB |
Output is correct |
| 9 |
Correct |
4 ms |
384 KB |
Output is correct |
| 10 |
Correct |
5 ms |
384 KB |
Output is correct |
| 11 |
Correct |
5 ms |
384 KB |
Output is correct |
| 12 |
Correct |
5 ms |
384 KB |
Output is correct |
| 13 |
Correct |
5 ms |
384 KB |
Output is correct |
| 14 |
Correct |
5 ms |
384 KB |
Output is correct |
| 15 |
Correct |
5 ms |
384 KB |
Output is correct |
| 16 |
Correct |
19 ms |
712 KB |
Output is correct |
| 17 |
Correct |
17 ms |
768 KB |
Output is correct |
| 18 |
Correct |
17 ms |
768 KB |
Output is correct |
| 19 |
Correct |
17 ms |
768 KB |
Output is correct |
| 20 |
Correct |
14 ms |
740 KB |
Output is correct |
| 21 |
Correct |
55 ms |
1912 KB |
Output is correct |
| 22 |
Correct |
59 ms |
1912 KB |
Output is correct |
| 23 |
Correct |
54 ms |
1912 KB |
Output is correct |
| 24 |
Correct |
54 ms |
1860 KB |
Output is correct |
| 25 |
Correct |
47 ms |
1912 KB |
Output is correct |
| 26 |
Correct |
54 ms |
1912 KB |
Output is correct |
| 27 |
Correct |
62 ms |
1912 KB |
Output is correct |
| 28 |
Correct |
56 ms |
1912 KB |
Output is correct |
| 29 |
Correct |
57 ms |
1868 KB |
Output is correct |
| 30 |
Correct |
42 ms |
1916 KB |
Output is correct |
| 31 |
Correct |
4 ms |
384 KB |
Output is correct |
| 32 |
Correct |
5 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
512 KB |
Output is correct |
| 4 |
Correct |
4 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
6 ms |
384 KB |
Output is correct |
| 9 |
Correct |
5 ms |
384 KB |
Output is correct |
| 10 |
Correct |
4 ms |
384 KB |
Output is correct |
| 11 |
Correct |
5 ms |
384 KB |
Output is correct |
| 12 |
Correct |
6 ms |
384 KB |
Output is correct |
| 13 |
Correct |
5 ms |
384 KB |
Output is correct |
| 14 |
Correct |
6 ms |
384 KB |
Output is correct |
| 15 |
Correct |
6 ms |
384 KB |
Output is correct |
| 16 |
Correct |
21 ms |
896 KB |
Output is correct |
| 17 |
Correct |
23 ms |
896 KB |
Output is correct |
| 18 |
Correct |
21 ms |
1024 KB |
Output is correct |
| 19 |
Correct |
20 ms |
896 KB |
Output is correct |
| 20 |
Correct |
13 ms |
512 KB |
Output is correct |
| 21 |
Correct |
82 ms |
2288 KB |
Output is correct |
| 22 |
Correct |
71 ms |
2288 KB |
Output is correct |
| 23 |
Correct |
79 ms |
2464 KB |
Output is correct |
| 24 |
Correct |
71 ms |
2304 KB |
Output is correct |
| 25 |
Correct |
68 ms |
3480 KB |
Output is correct |
| 26 |
Correct |
75 ms |
2288 KB |
Output is correct |
| 27 |
Correct |
78 ms |
2288 KB |
Output is correct |
| 28 |
Correct |
78 ms |
2288 KB |
Output is correct |
| 29 |
Correct |
82 ms |
2288 KB |
Output is correct |
| 30 |
Correct |
41 ms |
1656 KB |
Output is correct |
| 31 |
Correct |
5 ms |
384 KB |
Output is correct |
| 32 |
Correct |
5 ms |
384 KB |
Output is correct |
