TMSLT - Editorial

editorial
, , ,
21

Can anyone explain me why we must use the bool array as in this example.?

Blockquote

s=d;
has[s]=1;//boolean has[1000001] 
arr[0]=s;
k=1;
for(i=1;i<n;++i)
{
   s = (((((a*(s*s)%m)%m)+((b*s)%m))%m)+(c%m))%m;
    if(has[s])
    {
        break;
    }
    else
    {
        arr[k++]=s;
        has[s]=1;
    }
}

if(i==n)flag=1;

for(i=0;i<k;++i)
{
    if(arr[i]==s)break;
}

pos=i;
22

Can anyone explain me why we must use the bool array as in this example.?

Blockquote

s=d;
has[s]=1;//boolean has[1000001] 
arr[0]=s;
k=1;
for(i=1;i<n;++i)
{
   s = (((((a*(s*s)%m)%m)+((b*s)%m))%m)+(c%m))%m;
    if(has[s])
    {
        break;
    }
    else
    {
        arr[k++]=s;
        has[s]=1;
    }
}

if(i==n)flag=1;

for(i=0;i<k;++i)
{
    if(arr[i]==s)break;
}

pos=i;
23

Can anyone explain me why we must use the bool array as in this example.?

Blockquote

s=d;
has[s]=1;//boolean has[1000001] 
arr[0]=s;
k=1;
for(i=1;i<n;++i)
{
   s = (((((a*(s*s)%m)%m)+((b*s)%m))%m)+(c%m))%m;
    if(has[s])
    {
        break;
    }
    else
    {
        arr[k++]=s;
        has[s]=1;
    }
}

if(i==n)flag=1;

for(i=0;i<k;++i)
{
    if(arr[i]==s)break;
}

pos=i;
24

Guys, I am getting SIGSEGV, please help.

Since the strength canā€™t be greater than 1000000, I used a boolean array s[1000000] of this size, true means the strength is taken by a person, if two persons are there with same strength then they would be in different teams and cancel out the difference of strengths, so for every strength temp that comes during iteration, I have used s[temp]=~s[temp] . Finally, I just add and subtract alternatively for every s[i]==true. Giving me SIGSEGVā€¦ please help.

#include<bits/stdc++.h>
using namespace std;

int main()
{
int t;
scanf("%d",&t);
while(t--)
{
    long n,a,b,c,d,i,diff=0,last;
    scanf("%ld%ld%ld%ld%ld",&n,&a,&b,&c,&d);
    bool s[1000000]={false};
    s[d]=true;
    last=d;
    for(i=1;i<n;i++)
    {
        long temp=(last*(a*last+b)+c)%1000000;
        s[temp]=(~(s[temp]));
        last=temp;
    }
    i=0;
    while(i<1000000)
    {
        if(s[i])
        {
            diff+=i;
            i++;
            while(i<1000000 && s[i]==false)
                i++;
            if(i<1000000)
            {
                diff-=i;
                i++;
            }
        }
        else i++;
    }
    if(diff>=0) printf("%ld\n",diff);
    else printf("%ld\n",diff-2*diff);
}
return 0;

}