Submission #371207

#	Time	Username	Problem	Language	Result	Execution time	Memory
371207		daniel920712	Intergalactic ship (IZhO19_xorsum)	C++14	47 / 100	2088 ms	44392 KiB

xorsum

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>

using namespace std;
long long all[200005];


pair < pair < long long , long long > , long long > tt[200005];
vector < long long > how,how2,how3;
long long con[105]={0};
long long con2[105]={0};
long long ttt[100005][155]={0};
long long ttt2[100005][155]={0};
long long ttt3[100005][155]={0};
long long Pow[200005]={0};
long long ans=0,N,M,MOD=1e9+7;
int main()
{
    long long i,j,k,l,m,x=1,y=1,z=1,ok=1,ans2=0,xx=0,yy,zz,a,b;
    scanf("%lld",&N);
    for(i=1;i<=N;i++) scanf("%lld",&all[i]);
    scanf("%lld",&M);
    Pow[0]=1;
    for(i=0;i<M;i++) Pow[i+1]=Pow[i]*2%MOD;
    for(i=0;i<M;i++) scanf("%lld %lld %lld",&tt[i].first.first,&tt[i].first.second,&tt[i].second);
    for(i=1;i<=N;i++)
    {
        how.clear();
        xx=0;
        for(j=0;j<M;j++)
        {
            if(tt[j].first.first<=i&&tt[j].first.second>=i)
            {
                how.push_back(tt[j].second);
                xx++;
            }
        }
        for(j=0;j<128;j++) ttt[0][j]=0;
        ttt[0][0]=1;
        for(j=0;j<xx;j++)
        {
            for(k=0;k<128;k++) ttt[j+1][k]=ttt[j][k];
            for(k=0;k<128;k++)
            {
                ttt[j+1][k^how[j]]+=ttt[j][k];
                ttt[j+1][k^how[j]]%=MOD;
            }
        }
        for(j=0;j<128;j++)
        {
            ans+=(all[i]^j)*(all[i]^j)%MOD*i%MOD*(N-i+1)%MOD*ttt[xx][j]%MOD*Pow[M-xx]%MOD;
            ans%=MOD;
        }
        for(j=i+1;j<=N;j++)
        {
            how.clear();
            how2.clear();
            how3.clear();
            xx=yy=zz=0;
            for(k=0;k<M;k++)
            {
                if(tt[k].first.first<=i&&tt[k].first.second>=j)
                {
                    how.push_back(tt[k].second);
                    xx++;
                }
                else if(tt[k].first.first<=i&&tt[k].first.second>=i)
                {
                    how2.push_back(tt[k].second);
                    yy++;
                }
                else if(tt[k].first.first<=j&&tt[k].first.second>=j)
                {
                    how3.push_back(tt[k].second);
                    zz++;
                }
            }


            for(k=0;k<128;k++) ttt[0][k]=0;
            ttt[0][0]=1;
            for(k=0;k<xx;k++)
            {
                for(l=0;l<128;l++) ttt[k+1][l]=ttt[k][l];
                for(l=0;l<128;l++)
                {
                    ttt[k+1][l^how[k]]+=ttt[k][l];
                    ttt[k+1][l^how[k]]%=MOD;
                }
            }


            for(k=0;k<128;k++) ttt2[0][k]=0;
            ttt2[0][0]=1;
            for(k=0;k<yy;k++)
            {
                for(l=0;l<128;l++) ttt2[k+1][l]=ttt2[k][l];
                for(l=0;l<128;l++)
                {
                    ttt2[k+1][l^how2[k]]+=ttt2[k][l];
                    ttt2[k+1][l^how2[k]]%=MOD;
                }
            }

            for(k=0;k<128;k++) ttt3[0][k]=0;
            ttt3[0][0]=1;
            for(k=0;k<zz;k++)
            {
                for(l=0;l<128;l++) ttt3[k+1][l]=ttt3[k][l];
                for(l=0;l<128;l++)
                {
                    ttt3[k+1][l^how3[k]]+=ttt3[k][l];
                    ttt3[k+1][l^how3[k]]%=MOD;
                }
            }

            for(m=0;m<128;m++)
            {
                a=0;
                b=0;
                for(k=0;k<128;k++)
                {
                    a+=(all[i]^k^m)*ttt2[yy][k];
                    b+=(all[j]^k^m)*ttt3[zz][k];
                    a%=MOD;
                    b%=MOD;
                }
                ans+=2*a*b%MOD*ttt[xx][m]%MOD*Pow[M-xx-yy-zz]%MOD*i%MOD*(N-j+1)%MOD;
            }



        }
    }
    printf("%lld\n",ans);
    return 0;
}
//936

Compilation message (stderr)

xorsum.cpp: In function 'int main()':
xorsum.cpp:21:25: warning: unused variable 'x' [-Wunused-variable]
   21 |     long long i,j,k,l,m,x=1,y=1,z=1,ok=1,ans2=0,xx=0,yy,zz,a,b;
      |                         ^
xorsum.cpp:21:29: warning: unused variable 'y' [-Wunused-variable]
   21 |     long long i,j,k,l,m,x=1,y=1,z=1,ok=1,ans2=0,xx=0,yy,zz,a,b;
      |                             ^
xorsum.cpp:21:33: warning: unused variable 'z' [-Wunused-variable]
   21 |     long long i,j,k,l,m,x=1,y=1,z=1,ok=1,ans2=0,xx=0,yy,zz,a,b;
      |                                 ^
xorsum.cpp:21:37: warning: unused variable 'ok' [-Wunused-variable]
   21 |     long long i,j,k,l,m,x=1,y=1,z=1,ok=1,ans2=0,xx=0,yy,zz,a,b;
      |                                     ^~
xorsum.cpp:21:42: warning: unused variable 'ans2' [-Wunused-variable]
   21 |     long long i,j,k,l,m,x=1,y=1,z=1,ok=1,ans2=0,xx=0,yy,zz,a,b;
      |                                          ^~~~
xorsum.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   22 |     scanf("%lld",&N);
      |     ~~~~~^~~~~~~~~~~
xorsum.cpp:23:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   23 |     for(i=1;i<=N;i++) scanf("%lld",&all[i]);
      |                       ~~~~~^~~~~~~~~~~~~~~~
xorsum.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   24 |     scanf("%lld",&M);
      |     ~~~~~^~~~~~~~~~~
xorsum.cpp:27:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   27 |     for(i=0;i<M;i++) scanf("%lld %lld %lld",&tt[i].first.first,&tt[i].first.second,&tt[i].second);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 0 / 6
• Subtask 4: 0 / 9
• Subtask 5: 8 / 8
• Subtask 6: 11 / 11
• Subtask 7: 19 / 19
• Subtask 8: 0 / 30
• Subtask 9: 0 / 8