Submission #713227

#	Time	Username	Problem	Language	Result	Execution time	Memory
713227		bin9638	Gap (APIO16_gap)	C++17	30 / 100	90 ms	89352 KiB

gap

#include <bits/stdc++.h>
 
#ifndef SKY
#include "gap.h"
#endif // SKY
 
using namespace std;
 
#define ll long long
#define pb push_back
#define N 200010
#define ii pair<int,int>
#define fs first
#define sc second
#define ld double
 
int n;
 
#ifdef SKY
ll a[N],am=-1,mn,mx;
void MinMax(ll s,ll t, ll *u, ll *v)
{
    if(s>t)
    {
        cout<<"NGU VC";
        exit(0);
    }
    if(s>a[n]||a[lower_bound(a+1,a+1+n,s)-a]>t)
    {
        mn=-1;
        mx=-1;
        return;
    }
    mn=a[lower_bound(a+1,a+1+n,s)-a];
    if(t>=a[n])
    {
        mx=a[n];
        return;
    }
    mx=a[prev(upper_bound(a+1,a+1+n,t))-a];
}
#endif
 
long long findGap(int T, int cc)
{
  	long long a[11111111];
  	memset(a, 0, sizeof a);
  	for (int i = 0; i < n; i++) a[i] = i ^ (i >> 1);
  	for (int i = 0; i < n; i++) a[i] = a[i] ^ (a[i] & (1 << i));
    n=cc;
    ll L=0,R=1e18;
    vector<ll>s;
  	int cnt=0;
    while(L<=R)
    {
      cnt++;
      if(cnt*2>(n+1))
        break;
        ll u,v;
        MinMax(L,R,&u,&v);
        #ifdef SKY
        u=mn;v=mx;
        #endif // SKY
        //cout<<L<<" "<<R<<" "<<u<<" "<<v<<endl;
        if(u==-1)
            break;
        s.pb(u);
        s.pb(v);
        L=u+1;
        R=v-1;
    }
    sort(s.begin(),s.end());
    s.erase(unique(s.begin(),s.end()),s.end());
    ll res=0;
    for(int i=0;i<s.size()-1;i++)
        res=max(res,s[i+1]-s[i]);
	return res;
}
 
#ifdef SKY
int main()
{
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    int n,T;
    cin>>T>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    cout<<findGap(T,n)<<endl;
    return 0;
}
#endif // SKY

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:75:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for(int i=0;i<s.size()-1;i++)
      |                 ~^~~~~~~~~~~
gap.cpp:75:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   75 |     for(int i=0;i<s.size()-1;i++)
      |     ^~~
gap.cpp:77:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   77 |  return res;
      |  ^~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 0 / 70