oj.uz

답안 #371209

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
371209 2021-02-26T05:34:12 Z daniel920712 Intergalactic ship (IZhO19_xorsum) C++14
19 / 100
 2000 ms 10348 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[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);
        if(tt[i].first.second-tt[i].first.first) ok=0;
    }
    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;
        }
        if(!ok)
        {
            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

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: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:29:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   29 |         scanf("%lld %lld %lld",&tt[i].first.first,&tt[i].first.second,&tt[i].second);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 165 ms 4844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2094 ms 364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 364 KB Output is correct
2 Correct 83 ms 464 KB Output is correct
3 Correct 82 ms 364 KB Output is correct

Subtask #6
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 364 KB Output is correct
2 Correct 83 ms 464 KB Output is correct
3 Correct 82 ms 364 KB Output is correct
4 Correct 1412 ms 9964 KB Output is correct
5 Correct 1395 ms 10124 KB Output is correct
6 Correct 1398 ms 10348 KB Output is correct
7 Correct 1399 ms 10092 KB Output is correct

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -