oj.uz

Submission #287016

# Submission time Handle Problem Language Result Execution time Memory
287016 2020-08-31T09:00:39 Z tqbfjotld Intergalactic ship (IZhO19_xorsum) C++14
0 / 100
 140 ms 640 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
///subtask 3 (i hope)

int MOD = 1000000007LL;
int modinv(int a);
int fastExp(int b, int a){
    if (a<0) return modinv(fastExp(b,-a));
    if (a==0) return 1;
    if (a&1) return (b*fastExp(b,a-1))%MOD;
    int t = fastExp(b,a>>1);
    return (t*t)%MOD;
}
int modinv(int a){
    return fastExp(a,MOD-2);
}

int orig[1005];
int occ[1005][35];
int l[100005];
int r[100005];
int v[100005];

int newv[1005];

int div2 = modinv(2);

main(){
    int n;
    scanf("%lld",&n);
    for (int x = 1; x<=n; x++){
        scanf("%lld",&orig[x]);
    }
    int q;
    scanf("%lld",&q);
   /* if ((n<=30 && q<=20) || (n<=100 && q<=10)){
        for (int x = 0; x<q; x++){
            scanf("%lld%lld%lld",&l[x],&r[x],&v[x]);
        }
        long long ans = 0;
        for (int bitmask = 0; bitmask<(1<<q); bitmask++){
            for (int x = 1; x<=n; x++){
                newv[x] = orig[x];
            }
            for (int x = 0; x<q; x++){
                if (bitmask & (1<<x)){
                    for (int y = l[x]; y<=r[x]; y++){
                        newv[y] ^= v[x];
                    }
                }
            }
            long long something = 0;
            long long tans = 0;
            for (int x = 1; x<=n; x++){
                tans += newv[x]*newv[x]*x*(n-x+1);
                tans += 2*newv[x]*(n-x+1)*something;
                tans %= 1000000007LL;
                something += newv[x]*x;
                something %= 1000000007LL;
            }
            ans += tans;
            ans %= 1000000007LL;
        }
        printf("%lld",ans);
        return 0;
    }*/
    for (int x = 1; x<=n; x++){
        for (int y = 0; y<32; y++){
            if (orig[x]==y){
                occ[x][y] = fastExp(2,q);
            }
            else occ[x][y] = 0;
        }
    }
    for (int x = 0; x<q; x++){
        int a,b,c;
        scanf("%lld%lld%lld",&a,&b,&c);
        vector<int> temp;
        for (int x = a; x<=b; x++){
            temp.clear();
            for (int y = 0; y<32; y++)
                temp.push_back((div2*occ[x][y^c])%MOD);
            for (int y = 0; y<32; y++){
                occ[x][y] *= div2;
                occ[x][y]%=MOD;
                occ[x][y] += temp[y];
                occ[x][y]%=MOD;
            }
        }
    }
    int someNumber = fastExp(2,-q);
    long long something = 0;
    long long tans = 0;
    for (int x = 1; x<=n; x++){
        int toAdd = 0;
        for (int y = 0; y<32; y++){
            int mult = occ[x][y];
            tans += (y*y*x*(n-x+1)*mult)%MOD;
            tans += 2*y*(n-x+1)*(something*mult)%MOD;
            tans %= MOD;
            toAdd += (y)*((someNumber*mult)%MOD)*x;
            toAdd %= MOD;
        }
        something += toAdd;
    }
    printf("%lld",tans);
}

Compilation message

xorsum.cpp:29:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   29 | main(){
      |      ^
xorsum.cpp: In function 'int main()':
xorsum.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   31 |     scanf("%lld",&n);
      |     ~~~~~^~~~~~~~~~~
xorsum.cpp:33:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |         scanf("%lld",&orig[x]);
      |         ~~~~~^~~~~~~~~~~~~~~~~
xorsum.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   36 |     scanf("%lld",&q);
      |     ~~~~~^~~~~~~~~~~
xorsum.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   78 |         scanf("%lld%lld%lld",&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 140 ms 400 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -