Submission #951904

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
951904	2024-03-22T22:27:47 Z	Sputnik123	Gap (APIO16_gap)	C++14	30 / 100	35 ms	5828 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<x;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	1 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	2 ms	4440 KB	Output is correct
5	Correct	1 ms	4440 KB	Output is correct
6	Correct	1 ms	4436 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	2 ms	4440 KB	Output is correct
12	Correct	2 ms	4440 KB	Output is correct
13	Correct	3 ms	4440 KB	Output is correct
14	Correct	2 ms	4440 KB	Output is correct
15	Correct	2 ms	4440 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	4620 KB	Output is correct
19	Correct	9 ms	4620 KB	Output is correct
20	Correct	7 ms	4612 KB	Output is correct
21	Correct	32 ms	5680 KB	Output is correct
22	Correct	32 ms	5684 KB	Output is correct
23	Correct	35 ms	5672 KB	Output is correct
24	Correct	33 ms	5592 KB	Output is correct
25	Correct	29 ms	5672 KB	Output is correct
26	Correct	33 ms	5828 KB	Output is correct
27	Correct	33 ms	5488 KB	Output is correct
28	Correct	32 ms	5684 KB	Output is correct
29	Correct	32 ms	5668 KB	Output is correct
30	Correct	27 ms	5592 KB	Output is correct
31	Correct	1 ms	4552 KB	Output is correct
32	Correct	1 ms	4440 KB	Output is correct

Subtask #2

0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4440 KB	Output is correct
2	Incorrect	1 ms	4440 KB	Output isn't correct
3	Incorrect	1 ms	4440 KB	Output isn't correct
4	Incorrect	1 ms	4436 KB	Output isn't correct
5	Correct	1 ms	4440 KB	Output is correct
6	Incorrect	1 ms	4440 KB	Output isn't correct
7	Incorrect	1 ms	4440 KB	Output isn't correct
8	Incorrect	1 ms	4440 KB	Output isn't correct
9	Incorrect	1 ms	4440 KB	Output isn't correct
10	Incorrect	1 ms	4440 KB	Output isn't correct
11	Incorrect	1 ms	4440 KB	Output isn't correct
12	Incorrect	1 ms	4440 KB	Output isn't correct
13	Incorrect	1 ms	4440 KB	Output isn't correct
14	Incorrect	1 ms	4440 KB	Output isn't correct
15	Correct	1 ms	4440 KB	Output is correct
16	Incorrect	4 ms	4632 KB	Output isn't correct
17	Incorrect	4 ms	4540 KB	Output isn't correct
18	Incorrect	4 ms	4636 KB	Output isn't correct
19	Incorrect	4 ms	4620 KB	Output isn't correct
20	Incorrect	2 ms	4608 KB	Output isn't correct
21	Incorrect	14 ms	4800 KB	Output isn't correct
22	Incorrect	13 ms	4900 KB	Output isn't correct
23	Incorrect	13 ms	4720 KB	Output isn't correct
24	Incorrect	13 ms	5004 KB	Output isn't correct
25	Correct	10 ms	4888 KB	Output is correct
26	Incorrect	13 ms	4912 KB	Output isn't correct
27	Incorrect	13 ms	4916 KB	Output isn't correct
28	Incorrect	13 ms	4900 KB	Output isn't correct
29	Incorrect	14 ms	4912 KB	Output isn't correct
30	Incorrect	8 ms	4904 KB	Output isn't correct
31	Incorrect	1 ms	4440 KB	Output isn't correct
32	Incorrect	1 ms	4440 KB	Output isn't correct