914 - Jumping Champion

[brianfry713]

Doesn't match the sample I/O.

[shuvokr]

For those who got continuously wrong answer

Code: Select all

Sample Input:
1
8 10

Ac output:
No jumping champion

[uDebug]

Replying to follow the thread.

[Wishu.here]

I am getting WA from this code...i have tried multiple inputs from different sites all have give me correct ans but i don't know why it is giving me WA in final submission.

Code: Select all

#include<iostream>
#include<bitset>
#include<vector>
#include<cmath>

using namespace std;

bitset<10000010> bs;
vector<long long> primes;
vector<long long> primesdiff;

void sieve(long long n)
{
    bs.reset();
    bs.flip();
    bs[0]=0;
    bs[1]=1;
    primes.push_back(1);

    for(long long i = 2;i<=(n+1);i++)
        {
            if(bs.test(size_t(i)))
                {
                    for(long long j=i*i;j<=n;j += i)
                        {
                            bs[j]=0;
                        }
                    primes.push_back((long long)i);
                }

        }

}


int main()
{
    sieve(10000000);
    long long n,u,l;
    cin >>n;

    while(n != 0)
        {
            cin >> l;
            cin >> u;

            int flag=0;
            for(long long i=1;i<primes.size();i++)
            {
                if(primes.at(i) >= l && flag == 0)
                    {
                        l=i;
                        flag =1;
                    }

                if(primes.at(i) == u)
                    {
                        u=i;
                        break;
                    }

                if(primes.at(i) > u)
                    {
                        u=i-1;
                        break;
                    }
            }

            long long maximum=0;
            long long j=0,k;
            k = u-l-1;
            for(long long i=l;i<u;i++)
                {
                    primesdiff.push_back(abs(primes.at(i)-primes.at(i+1)));

                    if(maximum <= primesdiff.at(j) && j<=k)
                        {
                            maximum = primesdiff.at(j);
                        }
                    j++;

                }


            long long signature[maximum];
            for(long long i=0;i<=maximum;i++)
                {
                        signature[i]=0;
                }

            for(long long i=0;i<primesdiff.size();i++)
                {
                    signature[primesdiff.at(i)]++;
                }

            long long highest=0;
            long long index;
            for(long long i=0;i<=maximum;i++)
                {
                    if(signature[i]>highest)
                        {
                            highest = signature[i];
                            index =i;
                        }
                }

            long long counter = 0;
            for(long long i=0;i<=maximum;i++)
                {
                    if(signature[i]==highest)
                        {
                            counter++;
                        }

                }

            if(counter >= 2)
                {
                    cout<<"No jumping champion"<<endl;

                }
            else if(counter < 2)
                {
                    cout<<"The jumping champion is "<<index<<endl;
                }


            primesdiff.clear();
            n--;
        }

    return 0;
}

Inputs that i have tried.

16
734 1561
56 1606
184 1075
382 501
741 1173
684 779
279 283
667 836
125 243
737 765
119 577
737 828
556 795
60 1901
793 1432
492113 492227

output:

16
734 1561
The jumping champion is 6
56 1606
The jumping champion is 6
184 1075
The jumping champion is 6
382 501
No jumping champion
741 1173
No jumping champion
684 779
The jumping champion is 8
279 283
The jumping champion is 2
667 836
No jumping champion
125 243
The jumping champion is 2
737 765
The jumping champion is 4
119 577
The jumping champion is 6
737 828
The jumping champion is 4
556 795
The jumping champion is 6
60 1901
The jumping champion is 6
793 1432
The jumping champion is 6
492113 492227
The jumping champion is 114

and also the given output of the problem. All have come correct ans. but still getting WA in final submission.

[lbv]

I am getting WA from this code...i have tried multiple inputs from different sites all have give me correct ans but i don't know why it is giving me WA in final submission.

A good idea is to always try test cases that go to the lower and upper boundaries specified in the problem statement.

For example, you may try:

Input

Code: Select all

4
0 0
0 1
1 1
999999 1000000

Output

Code: Select all

No jumping champion
No jumping champion
No jumping champion
No jumping champion

[brianfry713]

Try input:

Code: Select all

1
92783 92783

[moudud99]

I am getting WA.tried inputs from this thread.
please help me.Thanks in advance.

Code: Select all

#include<bits/stdc++.h>
#define FRU freopen("out.txt","w",stdout)
#define FRO freopen("in.txt","r",stdin)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(ara,n) memset(ara,n,sizeof ara)
#define loop(i,j,n) for(i=j;i<n;i++)
#define rloop(i,j,n) for(i=n;i>=j;i--)
#define INF 2147483647
//const int row[]={-1, -1, -1,  0,  0,  1,  1,  1};  // Kings Move
//const int col[]={-1,  0,  1, -1,  1, -1,  0,  1};  // Kings Move
//const int row[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int col[]={-1,  1, -2,  2, -2,  2, -1,  1};  // Knights Move
//const int row[]={-1,0,0,1,0};
//const int col[]={0,-1,1,0,0};
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
int lcm(int a,int b){return ((a*b)/gcd(a,b));}

#define Max 2000000
int prime_int[Max];
bool prime_bool[Max];
void prime_num()
{
    memset(prime_bool,true,sizeof prime_bool);
    int i,j,root=sqrt(Max);
    //prime_bool[0]=prime_bool[1]=false;
    for(i=4;i<=Max;i+=2)prime_bool[i]=false;//marking even numbers
    for(i=3;i<=root;i+=2)if(prime_bool[i]==true)
    {
        for(j=i*i;j<=Max;j+=2*i)prime_bool[j]=false;//marking composit numbers
    }
    prime_int[0]=2;
    for(i=3,j=1;i<Max;i+=2)if(prime_bool[i]==true)prime_int[j++]=i;

}

using namespace std;

int main()
{
//FRO;
//FRU;
//std::ios_base::sync_with_stdio(false);
    int a,b,c,i,j,k,tc,t;
    int n,m,cnt=0;
    map<int,int>mmp;
    vector<int>list;

    scanf("%d",&tc);
    prime_num();
    while(tc--)
    {
        mmp.clear();
        list.clear();
        pair<int,int>pp[100005];
        scanf("%d%d",&n,&m);
        if(n>m)swap(n,m);
        if(n==m)
        {
            printf("No jumping champion\n");
            continue;
        }
        int flag=0;
        for(i=0;i<m;i++)
        {
            if(prime_int[i]>m)
            {flag=0;
                break;
            }
            if(prime_int[i]>=n && prime_int[i]<m && flag==0)
            {
                flag=1;
                j=i;
                continue;
            }
            if(flag==1 && prime_int[i]>n && prime_int[i]<=m)
            {
                flag=2;
                break;
            }
        }
        if(flag<2)
        {
            printf("No jumping champion\n");
            continue;
        }
        i=j+1;
        for(;prime_int[i]<=m;i++)
        {
            int val=prime_int[i]-prime_int[i-1];
            {
                if(mmp.find(val)==mmp.end())
                {
                    list.pb(val);
                }
                mmp[val]++;
            }
        }
        for(i=0;i<list.size();i++)
        {
            pp[i]=mp(mmp[list[i]],list[i]);
        }
        sort(pp,pp+list.size());
        flag=0;
        if(pp[list.size()-1].ff==pp[list.size()-2].ff)flag=1;
        if(flag==1 || list.size()<1)
        {
            printf("No jumping champion\n");
        }
        if(!flag)
        {
            printf("The jumping champion is %d\n",pp[list.size()-1].ss);
        }
    }

return 0;
}

[aseem_cu]

Code: Select all

//----->|try=0; while(!success) try++;|<------
//----->|Belief Yourself,Respect Yourself|<----
#include<bits/stdc++.h>
using namespace std;
#define max3(a,b,c) max(max(a,b),c)
#define min3(a,b,c) min(min(a,b),c)
#define PI acos(-1.0)
#define LL long long
#define INF_MAX 2147483647
#define INF_MIN -2147483647
#define MX 10000010
#define MOD 1000000007
int arr[MX];
int isprime[MX];
void siv()
{
    memset(isprime,1,sizeof(isprime));
    for(int i=2; i<=MX; i++)
    {
        if(isprime[i])
        {
            for(int j=2; j*i<=MX; j++)
            {
                isprime[i*j]=0;
            }
        }
    }
    isprime[1]=0;
}
int main()
{
    //freopen("a.in", "r", stdin);
    //freopen("a.out", "w", stdout);
    siv();
    int test,lower,upper,temp,keep,temp1;
    map<int,int>mymap;
    map<int,int>::iterator it,itt;
    vector<int>v1,v2;
    set<int>s;
    cin>>test;
    while(test--)
    {
        v1.clear();
        v2.clear();
        mymap.clear();
        s.clear();
        //s1.clear();
        int t=0;
        cin>>lower>>upper;
        if(lower>upper)
        {
            temp=lower;
            lower=upper;
            upper=temp;
        }
        //cout<<"isprime check = "<<endl;
        for(int i=lower; i<=upper; i++)
        {
            if(isprime[i])
            {
                v1.push_back(i);
                //cout<<"i = "<<i<<endl;
            }
        }
        //cout<<"v1.size   =  "<<v1.size()<<endl;
        if(v1.size()<2)
        {
            cout<<"No jumping champion"<<endl;
            continue;
        }
        for(int i=0; i<v1.size()-1; i++)
        {
            keep=v1[i+1]-v1[i];
            mymap[keep]++;
            //cout<<"keep = "<<keep<<endl;
            s.insert(keep);
            v2.push_back(keep);
        }
        if(mymap.size()==1)
        {
            cout<<"The jumping champion is "<<keep<<endl;
            continue;
        }
        int maximum=0,res=0,flag=0;
        for(it=mymap.begin(); it!=mymap.end(); it++)
        {
            //cout<<it->first<<" "<<it->second<<endl;
           // s1.insert(it->second);
            if(maximum<it->second)
            {
                maximum=it->second;
                res=it->first;
            }
        }
        //cout<<"maximum = "<<maximum<<endl;
        int cnt=0;
        for(itt=mymap.begin(); itt!=mymap.end(); itt++)
        {
            if(maximum==itt->second && maximum!=1)
            {
                cnt++;
            }
        }
        //cout<<"cnt = "<<cnt<<endl;
        //cout<<"set size = "<<s.size()<<endl;
        //cout<<"v2 size = "<<v2.size()<<endl;
        if(s.size()==v2.size())
            cout<<"No jumping champion"<<endl;
        else if(cnt>1)
            cout<<"No jumping champion"<<endl;
        else
            cout<<"The jumping champion is "<<res<<endl;



    }
}