oj.uz

Submission #371205

# Submission time Handle Problem Language Result Execution time Memory
371205 2021-02-26T05:22:47 Z daniel920712 Intergalactic ship (IZhO19_xorsum) C++14
19 / 100
 2000 ms 4460 KB 
#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[35]={0};
long long con2[35]={0};
long long ttt[100005][35]={0};
long long ttt2[100005][35]={0};
long long ttt3[100005][35]={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;
    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<32;j++) ttt[0][j]=0;
        ttt[0][0]=1;
        for(j=0;j<xx;j++)
        {
            for(k=0;k<32;k++) ttt[j+1][k]=ttt[j][k];
            for(k=0;k<32;k++)
            {
                ttt[j+1][k^how[j]]+=ttt[j][k];
                ttt[j+1][k^how[j]]%=MOD;
            }
        }
        for(j=0;j<32;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<32;k++) ttt[0][k]=0;
            ttt[0][0]=1;
            for(k=0;k<xx;k++)
            {
                for(l=0;l<32;l++) ttt[k+1][l]=ttt[k][l];
                for(l=0;l<32;l++)
                {
                    ttt[k+1][l^how[k]]+=ttt[k][l];
                    ttt[k+1][l^how[k]]%=MOD;
                }
            }


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

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

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


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

Compilation message

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;
      |                         ^
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;
      |                             ^
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;
      |                                 ^
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;
      |                                     ^~
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;
      |                                          ^~~~
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
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 15 ms 364 KB Output is correct
3 Incorrect 62 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 15 ms 364 KB Output is correct
3 Incorrect 62 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2077 ms 4460 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2069 ms 364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 604 ms 496 KB Output is correct
2 Correct 599 ms 492 KB Output is correct
3 Correct 601 ms 620 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 604 ms 496 KB Output is correct
2 Correct 599 ms 492 KB Output is correct
3 Correct 601 ms 620 KB Output is correct
4 Correct 1168 ms 2848 KB Output is correct
5 Correct 1163 ms 2796 KB Output is correct
6 Correct 1162 ms 2984 KB Output is correct
7 Correct 1163 ms 2960 KB Output is correct

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 15 ms 364 KB Output is correct
3 Incorrect 62 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 15 ms 364 KB Output is correct
3 Incorrect 62 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 15 ms 364 KB Output is correct
3 Incorrect 62 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -