oj.uz

Submission #1035547

# Submission time Handle Problem Language Result Execution time Memory
1035547 2024-07-26T11:49:17 Z alexander707070 Intergalactic ship (IZhO19_xorsum) C++14
17 / 100
 2000 ms 26824 KB 
#include<bits/stdc++.h>
#define MAXN 1007
using namespace std;

struct query{
    int type,val;
};

const int maxa=128;
const long long mod=1e9+7;

int n,d[MAXN],q,l[MAXN],r[MAXN],x[MAXN];

long long dp[500][150][150];
long long power[100007];
long long cnt[MAXN][MAXN],ans;

vector<query> w;
int li[207][3],tim,rest;

void calcdp(){
    dp[0][0][0]=1;

    for(int pos=1;pos<=int(w.size());pos++){
        for(int s=0;s<maxa;s++){
            for(int t=0;t<maxa;t++){
                dp[pos][s][t]=dp[pos-1][s][t];

                if(w[pos-1].type==0){
                    dp[pos][s][t]+=dp[pos-1][s^w[pos-1].val][t];
                }

                if(w[pos-1].type==1){
                    dp[pos][s][t]+=dp[pos-1][s][t^w[pos-1].val];
                }

                if(w[pos-1].type==2){
                    dp[pos][s][t]+=dp[pos-1][s^w[pos-1].val][t^w[pos-1].val];
                }

                dp[pos][s][t]%=mod;
            }
        }
    }
}

bool in(int a,int l,int r){
    return a>=l and a<=r;
}

long long calc(int a,int b){
    long long res=0;

    rest=0; tim++;
    w.clear();

    for(int i=1;i<=q;i++){
        if(!in(a,l[i],r[i]) and !in(b,l[i],r[i]))rest++;

        if(in(a,l[i],r[i]) and !in(b,l[i],r[i])){
            w.push_back({0,x[i]});
            li[x[i]][0]=tim;
        }
        if(!in(a,l[i],r[i]) and in(b,l[i],r[i])){
            w.push_back({1,x[i]});
            li[x[i]][1]=tim;
        }
        if(in(a,l[i],r[i]) and in(b,l[i],r[i])){
            w.push_back({2,x[i]});
            li[x[i]][2]=tim;
        }
    }

    calcdp();

    for(long long s=0;s<maxa;s++){
        for(long long t=0;t<maxa;t++){
            res+=((s*t*cnt[a][b])%mod) * ((dp[int(w.size())][d[a]^s][d[b]^t]*power[rest])%mod);
            res%=mod;
        }
    }

    return res;
}

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>d[i];
    }

    for(int i=1;i<=n;i++){
        for(int f=i;f<=n;f++){
            cnt[i][f]=i*(n-f+1);
            if(i!=f)cnt[i][f]*=2;
        }
    }

    cin>>q;
    for(int i=1;i<=q;i++){
        cin>>l[i]>>r[i]>>x[i];
    }

    power[0]=1;
    for(int i=1;i<=q;i++){
        power[i]=(power[i-1]*2)%mod;
    }

    for(int i=1;i<=n;i++){
        for(int f=i;f<=n;f++){
            ans+=calc(i,f);
            ans%=mod;
        }
    }

    cout<<ans<<"\n";
 
    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 18 ms 1928 KB Output is correct
4 Correct 19 ms 1928 KB Output is correct
5 Correct 10 ms 1624 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 18 ms 1928 KB Output is correct
4 Correct 19 ms 1928 KB Output is correct
5 Correct 10 ms 1624 KB Output is correct
6 Correct 1589 ms 2156 KB Output is correct
7 Correct 470 ms 1544 KB Output is correct
8 Correct 1663 ms 2388 KB Output is correct

Subtask #3
0 / 6.0

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

Subtask #4
0 / 9.0

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

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 2900 KB Output is correct
2 Correct 231 ms 3180 KB Output is correct
3 Correct 195 ms 3156 KB Output is correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 2900 KB Output is correct
2 Correct 231 ms 3180 KB Output is correct
3 Correct 195 ms 3156 KB Output is correct
4 Incorrect 299 ms 3884 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 18 ms 1928 KB Output is correct
4 Correct 19 ms 1928 KB Output is correct
5 Correct 10 ms 1624 KB Output is correct
6 Correct 1589 ms 2156 KB Output is correct
7 Correct 470 ms 1544 KB Output is correct
8 Correct 1663 ms 2388 KB Output is correct
9 Correct 217 ms 2900 KB Output is correct
10 Correct 231 ms 3180 KB Output is correct
11 Correct 195 ms 3156 KB Output is correct
12 Execution timed out 2044 ms 26824 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 18 ms 1928 KB Output is correct
4 Correct 19 ms 1928 KB Output is correct
5 Correct 10 ms 1624 KB Output is correct
6 Correct 1589 ms 2156 KB Output is correct
7 Correct 470 ms 1544 KB Output is correct
8 Correct 1663 ms 2388 KB Output is correct
9 Correct 217 ms 2900 KB Output is correct
10 Correct 231 ms 3180 KB Output is correct
11 Correct 195 ms 3156 KB Output is correct
12 Incorrect 299 ms 3884 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 18 ms 1928 KB Output is correct
4 Correct 19 ms 1928 KB Output is correct
5 Correct 10 ms 1624 KB Output is correct
6 Correct 1589 ms 2156 KB Output is correct
7 Correct 470 ms 1544 KB Output is correct
8 Correct 1663 ms 2388 KB Output is correct
9 Incorrect 566 ms 1872 KB Output isn't correct
10 Halted 0 ms 0 KB -