Submission #15274

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
15274	2015-07-12T05:11:18 Z	gs13068	로봇 심판의 님 게임 (kriii3_F)	C++	0 / 79	2000 ms	1084 KB

S

#include<cstdio>
#include<algorithm>

long long a[22],b[22],c[22];
int p[22],q[22],pn,qn;

long long gcd(long long a,long long b)
{
    return a?gcd(b%a,a):b;
}

long long lcm(long long a,long long b)
{
    long long g = gcd(a,b);
    if(std::min(a,b)/g>1000000)return 1e12+1;
    a*=b/g;
    return a<1e12+1?a:1e12+1;
}

long long togrundy(long long x)
{
    int i,j,k,l,t;
    long long r=0,lc;
    for(i=0;i<(1<<pn);i++)for(j=1;j<(1<<qn);j++)
    {
        lc=1;
        t=0;
        for(k=0;k<pn;k++)if((i>>k)&1)
        {
            if(lc>x)break;
            t++;
            lc=lcm(lc,p[k]);
        }
        for(l=0;l<qn;l++)if((j>>l)&1)
        {
            if(lc>x)break;
            t++;
            lc=lcm(lc,q[l]);
        }
        if(lc>x)continue;
        if(t%2)r+=x/lc;
        else r-=x/lc;
    }
    return r;
}

long long tonumber(long long x)
{
    long long l=x,r=1e12,mid;
    while(l<r)
    {
        mid=(l+r+1)/2;
        if(togrundy(mid)>x)r=mid-1;
        else l=mid;
    }
    return l;
}

int main()
{
    long long xo=0;
    int i,j,k,n;
    scanf("%d%d%d",&pn,&qn,&n);
    for(i=0;i<pn;i++)scanf("%d",&p[i]);
    for(i=0;i<qn;i++)scanf("%d",&q[i]);
    for(i=0;i<n;i++)
    {
        scanf("%lld",&a[i]);
        b[i]=togrundy(a[i]);
        xo^=b[i];
    }
    for(i=0;i<n;i++)
    {
        for(j=0;j<pn;j++)if(a[i]%p[j]==0)break;
        if(j<pn)
        {
            puts("0 0");
            continue;
        }
        for(k=0;k<qn;k++)if(a[i]%q[k]==0)break;
        if(k==qn)
        {
            puts("0 0");
            continue;
        }
        if((b[i]^xo)<b[i])
        {
            c[i]=tonumber(b[i]^xo);
            printf("1 %lld\n",a[i]-c[i]);
        }
        else puts("0 0");
    }
}

Subtask #1

0.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2000 ms	1084 KB	Program timed out
2	Halted	0 ms	0 KB	-

Subtask #2

0.0 / 51.0

#	Verdict	Execution time	Memory	Grader output
1	Halted	0 ms	0 KB	-