GreedyXploit's blog

By GreedyXploit, history, 3 months ago, In English

QUESTION LINK

MY CODE _

#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>

using namespace std;

vector<long long> SimpleSieve( vector<long long>& primes)
{
	//vector<long long> primes;
	bool isprime[10001]; // 10^5
	for(long long  i = 0 ; i<=10000 ; i++)
		isprime[i] = true;

	for(long long i = 2 ; i*i<=10000 ; i++)
	{
		if(isprime[i])
		{
			
			for(long long j = i*i ; j<=10000 ; j+=i)
				isprime[j] = false;
		}
	}
	for(int i = 0 ; i<=10000 ; i++){
		if(i == 1 || i == 0) continue;
		if(isprime[i] )
			primes.push_back(i);
	}
	return primes;
	
}

int main()
{
	int t;
	cin>>t;
	vector<long long> primes;
	SimpleSieve(primes);
	//for(auto i : primes)
	//	cout<<i<<"\n";

	while(t--){
		long long l , r;
		cin>>l>>r;
		///long long rsqrt = sqrt(r);
	
	bool is_prime[r-l+1];
	for(long long  i =0 ; i<=r-l ; i++)
	{
		is_prime[i] = true;
	}	
		//cout<<i;
	for(long long  i = 0 ;primes[i]*(long long)primes[i]<=r ; i++)
	{
		long long currprime = primes[i];
		//cout<<currprime<<"C"<<"\n";
		long long base = (l/currprime)*(currprime);
		if(base<l)
			base = base + currprime;
		for(long long j = base ; j<=r ; j+=currprime)
		{
			is_prime[j-l] = false;
	
		}	
		if(base == currprime)
			is_prime[base - l] = true;
	}
	
	
	for(long long i = 0 ; i<=r-l; i++)
	{
		if(is_prime[i] == true)
			cout<<i+l<<"\n";
	}
	}
}

Read more »

 
 
 
 
  • Vote: I like it
  • -35
  • Vote: I do not like it

By GreedyXploit, history, 3 months ago, In English

I am learning Segmented Sieve but i don't know why my program freezes when i give input to find primes between 1 to 10

here is my code pls say what is my error and how do i solve it

#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>

using namespace std;

vector<long long> SimpleSieve(long long rsqrt)
{
	vector<long long> primes;
	bool isprime[rsqrt+1];
	for(long long  i = 0 ; i<=rsqrt ; i++)
		isprime[i] = true;

	for(long long i = 2 ; i<=rsqrt ; i++)
	{
		if(isprime[i])
		{
			primes.push_back(i);
			for(long long j = i*i ; j<=rsqrt ; j+=i)
				isprime[j] = false;
		}
	}
	return primes;
	
}

int main()
{
	long long  l , r;
	cin>>l>>r;
	long long rsqrt = sqrt(r);
	vector<long long>primes = SimpleSieve(rsqrt);

	bool is_prime[r-l+1];
	for(long long  i =0 ; i<=r-l ; i++)
	{
		is_prime[i] = true;
	}	

	for(long long  i = 0 ;primes[i]*primes[i]<=r ; i++)
	{
		long long base = (l/primes[i])*(primes[i]);
		if(base<l)
			base = base + primes[i];
		
		for(long long j = base ; j<=r ; j+=primes[i])
		{
			is_prime[j-l] = false;
	
		}	
		if(base == primes[i])
			is_prime[base - l] = true;
	}
	
	for(long long i = 0 ; i<=r-l; i++)
	{
		if(is_prime[i] == true)
			cout<<i+l<<"\n";
	}
}

Read more »

 
 
 
 
  • Vote: I like it
  • -3
  • Vote: I do not like it

By GreedyXploit, history, 6 months ago, In English

QUESTION LINK

    #include<iostream>
    #include<algorithm>
    #include<vector>
    using namespace std;
     
    int main()
    {
        long long n ; //floors
        long long m ; //letters
     
        cin>>n;
        cin>>m;
        long long total = 0;
        vector<long long >a;
        for(long long  i = 0 ; i<n;i++)
        {
            long long k;
            cin>>k;
            total += k;
            a.push_back(total);
        }
     
        //cin>>m;
        vector<long long>b;
        for(int i = 0 ; i<m;i++)
        {
            long long k ;
            cin>>k;
            b.push_back(k);
        }
        
        for(long long  i = 0 ; i<m ; i++)
        {
            long long letter = b[i];
            auto f = lower_bound(a.begin() , a.end() , letter) - a.begin();
            vector<long long>c;
            long long  j = (f == 0)?1:a[f-1];
            while(j<=a[f])
            {
                c.push_back(j);
                ++j;
            }
            auto r = lower_bound(c.begin() , c.end() , letter) - c.begin();
            if(letter<=10)
            cout<<f+1<<" "<<r+1<<"\n";
            else
            cout<<f+1<<" "<<r<<"\n";
        }
    }
     

THIS IS MY code but it is having MEMORY LIMIT EXCEEDED

pls guys give a detailed solution code.And also say what is wrong in my code

Read more »

 
 
 
 
  • Vote: I like it
  • -22
  • Vote: I do not like it

By GreedyXploit, history, 6 months ago, In English
#include<bits/stdc++.h>
using namespace std;
int ct = 0;int ans = 0;
vector<int> a[5000+1];
bool checked[5000+1] = {false};

void dfs(int u )
{
    if(checked[u])
    {
       // cout<<u<<"\n";
        ans++;
        return;
    }
    //cout<<ans<<"\n";
    checked[u] = true;

    for(int i = 0 ; i<a[u].size() ; i++)
    {
        dfs(a[u][i]);
    }

}
int main()
{
    int n ;
    cin>>n;
    for(int i = 1 ; i<n;i++ )
    {
        int k ; 
        cin>>k;
        a[i].push_back(k);

    }
    
    dfs(1);
    //for(int i = 0 ; i<5 ; i++)
    //cout<<checked[i]<<"\n";   
    if(ans > 0)
    cout<<"YES";
    else
    cout<<"NO";
}

QUESTION LINK

THE TEST CASE IN WHICH I FAIL

test case 3 : 3 3 1 2

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By GreedyXploit, history, 6 months ago, In English

i tried it all day but don't know how to code the logic.Pls write a detailed code in c++ PLZZZZ QUESTION--->>

Read more »

 
 
 
 
  • Vote: I like it
  • -22
  • Vote: I do not like it

By GreedyXploit, history, 6 months ago, In English

QUESTION LINK

#include <iostream>
#include<algorithm>
using namespace std;
int binarySearch(int left , int right , int a[] , int n)
{
    int c = 0;
    for(int i = left; i<=right ; i++)
    {
        int l = -1;
        int r = n;
        while(r>l+1)
        {
            int mid = (l+r)/2;
            if(a[mid] >= i)
            {
                r = mid;
                //cout<<a[r]<<"\n";
            }

            else
                l = mid;

        }

        if(r<n && a[r] == i)
        {
            ++c;
            if(count(a , a + n , i) > 1)
                c = c+(count(a , a + n , i)-1);

        }

    }
    return c;
}

int main()
{
    int n ;
    cin>>n;
    int a[n];
    for(int i = 0 ; i<n;i++)
        cin>>a[i];
    int k;
    cin>>k;
    sort(a , a+n);
    for(int i = 0 ; i<k;i++)
    {
        int l , r;
        cin>>l>>r;
        cout<<binarySearch(l , r , a , n)<<"\n";
    }

    return 0;
}

Read more »

 
 
 
 
  • Vote: I like it
  • -7
  • Vote: I do not like it