oj.uz

Submission #1035582

# Submission time Handle Problem Language Result Execution time Memory
1035582 2024-07-26T12:08:36 Z alexander707070 Intergalactic ship (IZhO19_xorsum) C++14
28 / 100
 2000 ms 19632 KB 
#include<bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#define MAXN 100007
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[507][150][150];
long long power[100007];
long long cnt[1007][1007],ans;
 
vector<query> w;
int li[207][3],tim,rest;
int br[207][3];
 
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++){
 
                if(w[pos-1].type==0){
                    dp[pos][s][t]=(dp[pos-1][s][t] + dp[pos-1][s^w[pos-1].val][t])*power[br[w[pos-1].val][0]-1];
                }
 
                if(w[pos-1].type==1){
                    dp[pos][s][t]=(dp[pos-1][s][t] + dp[pos-1][s][t^w[pos-1].val])*power[br[w[pos-1].val][1]-1];
                }
 
                if(w[pos-1].type==2){
                    dp[pos][s][t]=(dp[pos-1][s][t] + dp[pos-1][s^w[pos-1].val][t^w[pos-1].val])*power[br[w[pos-1].val][2]-1];
                }
 
                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=0;i<=200;i++){
        for(int f=0;f<3;f++)br[i][f]=0;
    }
 
    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])){
            if(li[x[i]][0]!=tim)w.push_back({0,x[i]});
            li[x[i]][0]=tim;
            br[x[i]][0]++;
        }
        if(!in(a,l[i],r[i]) and in(b,l[i],r[i])){
            if(li[x[i]][1]!=tim)w.push_back({1,x[i]});
            li[x[i]][1]=tim;
            br[x[i]][1]++;
        }
        if(in(a,l[i],r[i]) and in(b,l[i],r[i])){
            if(li[x[i]][2]!=tim)w.push_back({2,x[i]});
            li[x[i]][2]=tim;
            br[x[i]][2]++;
        }
    }
 
    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 1 ms 348 KB Output is correct
3 Correct 16 ms 1920 KB Output is correct
4 Correct 18 ms 1884 KB Output is correct
5 Correct 8 ms 1372 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 1 ms 348 KB Output is correct
3 Correct 16 ms 1920 KB Output is correct
4 Correct 18 ms 1884 KB Output is correct
5 Correct 8 ms 1372 KB Output is correct
6 Correct 1040 ms 2160 KB Output is correct
7 Correct 384 ms 1476 KB Output is correct
8 Correct 796 ms 1528 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2053 ms 13400 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 2057 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 152 ms 2900 KB Output is correct
2 Correct 167 ms 2764 KB Output is correct
3 Correct 149 ms 2896 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 2900 KB Output is correct
2 Correct 167 ms 2764 KB Output is correct
3 Correct 149 ms 2896 KB Output is correct
4 Correct 1414 ms 15540 KB Output is correct
5 Correct 1494 ms 15536 KB Output is correct
6 Correct 1559 ms 15444 KB Output is correct
7 Correct 1544 ms 15444 KB Output is correct

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 16 ms 1920 KB Output is correct
4 Correct 18 ms 1884 KB Output is correct
5 Correct 8 ms 1372 KB Output is correct
6 Correct 1040 ms 2160 KB Output is correct
7 Correct 384 ms 1476 KB Output is correct
8 Correct 796 ms 1528 KB Output is correct
9 Correct 152 ms 2900 KB Output is correct
10 Correct 167 ms 2764 KB Output is correct
11 Correct 149 ms 2896 KB Output is correct
12 Execution timed out 2015 ms 19632 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 1 ms 348 KB Output is correct
3 Correct 16 ms 1920 KB Output is correct
4 Correct 18 ms 1884 KB Output is correct
5 Correct 8 ms 1372 KB Output is correct
6 Correct 1040 ms 2160 KB Output is correct
7 Correct 384 ms 1476 KB Output is correct
8 Correct 796 ms 1528 KB Output is correct
9 Correct 152 ms 2900 KB Output is correct
10 Correct 167 ms 2764 KB Output is correct
11 Correct 149 ms 2896 KB Output is correct
12 Correct 1414 ms 15540 KB Output is correct
13 Correct 1494 ms 15536 KB Output is correct
14 Correct 1559 ms 15444 KB Output is correct
15 Correct 1544 ms 15444 KB Output is correct
16 Execution timed out 2015 ms 19632 KB Time limit exceeded
17 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 1 ms 348 KB Output is correct
3 Correct 16 ms 1920 KB Output is correct
4 Correct 18 ms 1884 KB Output is correct
5 Correct 8 ms 1372 KB Output is correct
6 Correct 1040 ms 2160 KB Output is correct
7 Correct 384 ms 1476 KB Output is correct
8 Correct 796 ms 1528 KB Output is correct
9 Execution timed out 2053 ms 13400 KB Time limit exceeded
10 Halted 0 ms 0 KB -