Submission #667395

#	Time	Username	Problem	Language	Result	Execution time	Memory
667395		MohammadAghil	Gap (APIO16_gap)	C++17	83.51 / 100	58 ms	3396 KiB

gap

      #include <bits/stdc++.h>
#include "gap.h"
//   #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
 using namespace std;
  typedef long long ll;
   typedef pair<ll, ll> pp;
     #define per(i,r,l) for(int i = (r); i >= (l); i--)
       #define rep(i,l,r) for(int i = (l); i < (r); i++)
          #define all(x) begin(x), end(x)
             #define sz(x) (int)(x).size()
                 #define pb push_back
                     #define ss second
                          #define ff first
                                  void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
void IOS(){
     cin.tie(0) -> sync_with_stdio(0);
     // #ifndef ONLINE_JUDGE
     //      #define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
     //      freopen("inp.txt", "r", stdin);
     //      freopen("out.txt", "w", stdout);
     // #else
     //      #define er(args ...) 0
     // #endif
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 1e9 + 9, maxn = 3e5 + 5, lg = 17, inf = ll(1e18) + 5, p = 9973;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll,md);return k*k%md*(b&1ll?a:1)%md;}
 
// ll a[maxn], n;

// void MinMax(ll s, ll t, ll &mn, ll &mx){
//      mn = mx = -1;
//      rep(i,0,n) {
//           if(a[i] >= s && a[i] <= t) {
//                if(mn == -1) mn = mx = a[i];
//                mn = min(mn, a[i]);
//                mx = max(mx, a[i]);
//           }
//      }
// }

ll findGap(int T, int N) {
     ll ans = 0;
     ll mn = 0, mx = inf;
     if(T == 1){
          N = (N + 1)>>1;
          vector<ll> a;
          while(mn <= mx && N--){
               MinMax(mn, mx, &mn, &mx);
               if(mn + 1){
                    a.pb(mn), a.pb(mx);
                    mn++, mx--;
               } else break;
          }
          sort(all(a));
          rep(i,1,sz(a)) ans = max(ans, a[i] - a[i-1]); 
     } else{
          MinMax(mn, mx, &mn, &mx);
          ll k = (mx - mn + N - 2)/(N - 1);
          ll cr = 0, X = mx;
          vector<ll> a;
          ans = k;
          while(cr < X){
               MinMax(cr, cr + k, &mn, &mx);
               if(mn + 1) a.pb(mn), a.pb(mx);
               cr += k + 1;
          }     
          sort(all(a));
          rep(i,1,sz(a)) ans = max(ans, a[i] - a[i-1]); 
     }
     return ans;
}

// int main(){ IOS();
//      int t = 1000;
//      while(t--){
//           n = rng()%10000 + 2;
//           ll ans = 0;
//           rep(i,0,n) {
//                a[i] = (i?a[i-1]:0) + rng()%10000 + 1;
//                if(i) ans = max(ans, a[i] - a[i-1]);
//           }
//           if(ans - findGap(1, n)){
//                rep(i,0,n) cout << a[i] << ' ';
//                cout << '\n';
//                return 0;
//           }
//      }
//      return 0;
// }

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