Submission #951905

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
951905	2024-03-22T22:29:13 Z	Sputnik123	Gap (APIO16_gap)	C++14	100 / 100	46 ms	5920 KB

gap

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <functional>
#include <cstdio>
#define pb push_back
#define in insert
#define pll pair<ll,ll>
#define vpl vector<pll>
#define vll vector <ll>
#define vl vector<ll>
///#define mp make_pair
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define endl "\n"
#define ll long long 
#define ull unsigned long long
using namespace std;
using namespace __gnu_pbds;
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt,fma")
const ll sz=1e5+5;
const ll inf=1e18;
const ll mod=1e9+7;
const ll P=47;
namespace number_theory {
	ll gcd(ll x, ll y) {
	  if (x == 0) return y;
	  if (y == 0) return x;
	  return gcd(y, x % y);
	}
    ll lcm(ll x,ll y)
    {
        return  (x/gcd(x,y))*y;
    }
	bool isprime(ll n) { 
	  if (n <= 1) return false; 
	  if (n <= 3) return true; 
	  
	  if (n % 2 == 0 || n % 3 == 0) return false; 
	  
	  for (ll i = 5; i * i <= n; i += 6) 
		if (n % i == 0 || n % (i+2) == 0) 
		  return false; 
	  
	  return true; 
	} 
	 
	bool prime[15000105]; 
	void sieve(int n) { 
	  for (ll i = 0; i <= n; i++) prime[i] = 1;
	  for (ll p = 2; p * p <= n; p++) { 
		if (prime[p] == true) { 
		  for (ll i = p * p; i <= n; i += p) 
			prime[i] = false; 
		} 
	  } 
	  prime[1] = prime[0] = 0;
	} 
	 
	vector<ll> primelist;
	bool __primes_generated__ = 0;
	 
	void genprimes(int n) {
	  __primes_generated__ = 1;
	  sieve(n + 1);
	  for (ll i = 2; i <= n; i++) if (prime[i]) primelist.push_back(i);
	}
	 
	vector<ll> factors(ll n) {
	  if (!__primes_generated__) {
		cerr << "False" << endl;
		exit(1);
	  }
	  vector<ll> facs;
	 
	  for (ll i = 0; primelist[i] * primelist[i] <= n && i < primelist.size(); i++) {
		if (n % primelist[i] == 0) {
		  while (n % primelist[i] == 0) {
			n /= primelist[i];
			facs.push_back(primelist[i]);
		  }
		}
	  }
	  if (n > 1) {
		facs.push_back(n);
	  }
	  sort(facs.begin(), facs.end());
	  return facs;
	}
	
	vector<ll> getdivs(ll n) {
    vector<ll> divs;
    for (ll i = 1; i * i <= n; i++) {
      if (n % i == 0) {
        divs.push_back(i);
        divs.push_back(n / i);
      }
    }
    set <ll> s;
    for(ll i: divs)
        s.in(i);
    vll res;
    for(auto i: s)
        res.pb(i);
    return res;
  }
}
namespace modop {
	ll madd(ll a, ll b) {
	  return (a + b) % mod;
	}
	ll msub(ll a, ll b) {
	  return (((a - b) % mod) + mod) % mod;
	}
	ll mmul(ll a, ll b) {
	  return ((a % mod) * (b % mod)) % mod;
	}
	ll mpow(ll base, ll exp) {
	  ll res = 1;
	  while (exp) {
		if (exp % 2 == 1){
			res = (res * base) % mod;
		}
		exp >>= 1;
		base = (base * base) % mod;
	  }
	  return res;
	}
	ll minv(ll base) {
	  return mpow(base, mod - 2);
	}
	ll mdiv(ll a, ll b) {
	  return mmul(a, minv(b));
	}
	
	const ll FACTORIAL_SIZE = 1.1e6;
	ll fact[FACTORIAL_SIZE], ifact[FACTORIAL_SIZE];
	bool __factorials_generated__ = 0;
	void gen_factorial(ll n) {
		__factorials_generated__ = 1;
		fact[0] = fact[1] = ifact[0] = ifact[1] = 1;
		
		for (ll i = 2; i <= n; i++) {
			fact[i] = (i * fact[i - 1]) % mod;
		}
		ifact[n] = minv(fact[n]);
		for (ll i = n - 1; i >= 2; i--) {
			ifact[i] = ((i + 1) * ifact[i + 1]) % mod;
		}
	}
	ll nck(ll n, ll k) {
		if (!__factorials_generated__) {
			cerr << "Call gen_factorial you dope" << endl;
			exit(1);
		}
		if (k < 0 || n < k) return 0;
		ll den = (ifact[k] * ifact[n - k]) % mod;
		return (den * fact[n]) % mod;
	}
}

using namespace modop;
using namespace number_theory;
#include "gap.h"
ll j=0;
ll a[100000];
ll findGap(int t,int n)
{
	if(t==1)
	{
		ll l=1,r=inf;
		ll mn,mx;
		for(ll i=0;i<(n+1)/2;i++)
		{
			MinMax(l,r,&mn,&mx);
			a[j++]=mn;
			a[j++]=mx;
			l=mn+1,r=mx-1;
		}
		sort(a,a+n);
		ll ans=0;
		for(ll i=0;i<n;i++)
		{
			ans=max(ans,a[i+1]-a[i]);
		}
		return ans;
	}
	else
	{
		ll mn, mx;
		MinMax(1,inf,&mn,&mx);
		ll s=(mx-mn+n-2)/(n-1);
		ll ans=s,x,y,l=mn,i;
		for(i=mn;i+s<mx;i+=s+1)
		{
			MinMax(i,i+s,&x,&y);
			if(x!=-1)
			{
				ans=max(ans,x-l);
				l=y;
			}
		}
		MinMax(i,mx,&x,&y);
		if(x!=-1)
			ans=max(ans,x-l);
		return ans;
	}
}

Compilation message

gap.cpp: In function 'std::vector<long long int> number_theory::factors(long long int)':
gap.cpp:82:57: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |    for (ll i = 0; primelist[i] * primelist[i] <= n && i < primelist.size(); i++) {
      |                                                       ~~^~~~~~~~~~~~~~~~~~

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2392 KB	Output is correct
2	Correct	2 ms	4440 KB	Output is correct
3	Correct	1 ms	4440 KB	Output is correct
4	Correct	1 ms	4440 KB	Output is correct
5	Correct	2 ms	4440 KB	Output is correct
6	Correct	2 ms	4480 KB	Output is correct
7	Correct	2 ms	4436 KB	Output is correct
8	Correct	1 ms	4440 KB	Output is correct
9	Correct	1 ms	4440 KB	Output is correct
10	Correct	1 ms	4440 KB	Output is correct
11	Correct	1 ms	4440 KB	Output is correct
12	Correct	1 ms	4440 KB	Output is correct
13	Correct	1 ms	4440 KB	Output is correct
14	Correct	1 ms	4440 KB	Output is correct
15	Correct	1 ms	4544 KB	Output is correct
16	Correct	9 ms	4628 KB	Output is correct
17	Correct	8 ms	4624 KB	Output is correct
18	Correct	9 ms	4628 KB	Output is correct
19	Correct	8 ms	4628 KB	Output is correct
20	Correct	7 ms	4616 KB	Output is correct
21	Correct	34 ms	5568 KB	Output is correct
22	Correct	32 ms	5680 KB	Output is correct
23	Correct	33 ms	5552 KB	Output is correct
24	Correct	36 ms	5920 KB	Output is correct
25	Correct	29 ms	5668 KB	Output is correct
26	Correct	33 ms	5668 KB	Output is correct
27	Correct	32 ms	5680 KB	Output is correct
28	Correct	36 ms	5676 KB	Output is correct
29	Correct	32 ms	5484 KB	Output is correct
30	Correct	27 ms	5668 KB	Output is correct
31	Correct	3 ms	4440 KB	Output is correct
32	Correct	1 ms	4440 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4440 KB	Output is correct
2	Correct	1 ms	4440 KB	Output is correct
3	Correct	1 ms	4440 KB	Output is correct
4	Correct	1 ms	4440 KB	Output is correct
5	Correct	1 ms	4440 KB	Output is correct
6	Correct	1 ms	4440 KB	Output is correct
7	Correct	1 ms	4440 KB	Output is correct
8	Correct	1 ms	4440 KB	Output is correct
9	Correct	1 ms	4440 KB	Output is correct
10	Correct	1 ms	4440 KB	Output is correct
11	Correct	1 ms	4440 KB	Output is correct
12	Correct	1 ms	4440 KB	Output is correct
13	Correct	1 ms	4440 KB	Output is correct
14	Correct	1 ms	4440 KB	Output is correct
15	Correct	1 ms	4440 KB	Output is correct
16	Correct	11 ms	4708 KB	Output is correct
17	Correct	11 ms	4628 KB	Output is correct
18	Correct	11 ms	4628 KB	Output is correct
19	Correct	12 ms	4624 KB	Output is correct
20	Correct	6 ms	4612 KB	Output is correct
21	Correct	41 ms	4828 KB	Output is correct
22	Correct	46 ms	4704 KB	Output is correct
23	Correct	40 ms	4916 KB	Output is correct
24	Correct	40 ms	4912 KB	Output is correct
25	Correct	38 ms	5140 KB	Output is correct
26	Correct	40 ms	4908 KB	Output is correct
27	Correct	41 ms	4916 KB	Output is correct
28	Correct	44 ms	4904 KB	Output is correct
29	Correct	39 ms	4908 KB	Output is correct
30	Correct	21 ms	4920 KB	Output is correct
31	Correct	1 ms	4440 KB	Output is correct
32	Correct	1 ms	4440 KB	Output is correct