oj.uz

Submission #852238

# Submission time Handle Problem Language Result Execution time Memory
852238 2023-09-21T13:21:55 Z 8pete8 Gap (APIO16_gap) C++17
100 / 100
 44 ms 2000 KB 
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset>
#include "gap.h"
using namespace std;
#define ll long long
#define f first
#define endl "\n"
//#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
#define ll long long
const int mxn=1e5,mod=1000000007,lg=20,root=1000,inf=1e18;
ll v[mxn+10];
ll findGap(int T,int N){
    ll mn,mx;
    ll ans=1;
    ll lmn=1,lmx=1e18;
    if(T==1){
        ll j=0;
        for(ll i=0;i<(N+1)/2;i++){
            MinMax(lmn,lmx,&mn,&mx);
            if(mn==-1)break;
            v[j++]=mn;
            v[j++]=mx;
            lmn=mn+1;
            lmx=mx-1;
        }
        sort(v,v+N);       
        for(int i=1;i<N;i++)ans=max(ans,v[i]-v[i-1]);
        return ans;
    }
    MinMax(1,1e18,&mn,&mx);
    ans=((mx-mn)/(N-1));//min max gap
    ll add=ans+1,cur=mn+1,l,r,last=mn;
    while(cur<mx){
        MinMax(cur,min(mx,cur+add-1),&l,&r);
        if(l!=-1){
            ans=max(ans,l-last);
            last=r;
        }
        cur+=add;
    }// 1 2 3 4 5 6 7 8 9 10
    return ans;
}

Compilation message

gap.cpp:30:54: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   30 | const int mxn=1e5,mod=1000000007,lg=20,root=1000,inf=1e18;
      |                                                      ^~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 596 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 9 ms 636 KB Output is correct
17 Correct 8 ms 648 KB Output is correct
18 Correct 8 ms 680 KB Output is correct
19 Correct 8 ms 876 KB Output is correct
20 Correct 7 ms 620 KB Output is correct
21 Correct 31 ms 2000 KB Output is correct
22 Correct 31 ms 1984 KB Output is correct
23 Correct 35 ms 1972 KB Output is correct
24 Correct 32 ms 1972 KB Output is correct
25 Correct 30 ms 1928 KB Output is correct
26 Correct 31 ms 1980 KB Output is correct
27 Correct 31 ms 1792 KB Output is correct
28 Correct 32 ms 1984 KB Output is correct
29 Correct 31 ms 1976 KB Output is correct
30 Correct 26 ms 1836 KB Output is correct
31 Correct 0 ms 344 KB Output is correct
32 Correct 0 ms 344 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 596 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 10 ms 652 KB Output is correct
17 Correct 10 ms 616 KB Output is correct
18 Correct 10 ms 644 KB Output is correct
19 Correct 10 ms 652 KB Output is correct
20 Correct 6 ms 616 KB Output is correct
21 Correct 44 ms 1228 KB Output is correct
22 Correct 41 ms 1216 KB Output is correct
23 Correct 40 ms 1352 KB Output is correct
24 Correct 40 ms 1216 KB Output is correct
25 Correct 42 ms 1208 KB Output is correct
26 Correct 41 ms 1220 KB Output is correct
27 Correct 43 ms 1216 KB Output is correct
28 Correct 42 ms 1216 KB Output is correct
29 Correct 41 ms 1224 KB Output is correct
30 Correct 24 ms 1212 KB Output is correct
31 Correct 1 ms 344 KB Output is correct
32 Correct 0 ms 344 KB Output is correct