oj.uz

Submission #679460

# Submission time Handle Problem Language Result Execution time Memory
679460 2023-01-08T10:03:35 Z grandmast3r Intergalactic ship (IZhO19_xorsum) C++17
17 / 100
 2000 ms 5844 KB 
#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define vi vector<int>
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;

const int MOD = 1e9 + 7;

int add(int a, int b){
    a += b;
    if (a >= MOD){
        a -= MOD;
    }
    return a;
}

int sub(int a, int b){
    a -= b;
    if (a < 0){
        a += MOD;
    }
    return a;
}

int mul(int a, int b){
    return (a * 1ll * b) % MOD;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    #ifdef ON_PC
        freopen("input.txt", "r", stdin);
    #endif
    // freopen("output.txt", "w", stdout);
    int T = 1;
    // cin >> T;
    while (T--){
        int n;
        cin >> n;
        vector<int> a(n + 1);
        for (int i = 1; i <= n; i++){
            cin >> a[i];
        }
        int q;
        cin >> q;
        vector<vector<int>> req(q);
        for (int id = 0; id < q; id++){
            req[id].resize(3);
            for (int i = 0; i < 3; i++){
                cin >> req[id][i];
            }
        }
        int res = 0;
        // for (int i = 1; i <= n; i++){
        //     for (int mask = 0; mask < (1 << q); mask++){
        //         int x = a[i];
        //         for (int j = 0; j < q; j++){
        //             if (mask & (1 << j)){
        //                 if (req[j][0] <= i && i <= req[j][1]){
        //                     x ^= req[j][2];
        //                 }
        //             }
        //         }
        //         res = add(res, mul(mul(x, x), mul(i, n - i + 1)));
        //     }
        // }
        for (int i = 1; i <= n; i++){
            for (int j = i; j <= n; j++){
                vector<vector<vector<int>>> dp0((1 << 7), vector<vector<int>>(7, vector<int>(2)));
                vector<vector<vector<int>>> dp1((1 << 7), vector<vector<int>>(7, vector<int>(2)));
                for (int k = 0; k < 7; k++){
                    dp0[a[i]][k][bool(a[j] & (1 << k))]++;
                }
                for (int w = 0; w < q; w++){
                    dp1 = dp0;
                    int x = 0;
                    int y = 0;
                    if (req[w][0] <= i && i <= req[w][1]){
                        x = req[w][2];
                    }
                    if (req[w][0] <= j && j <= req[w][1]){
                        y = req[w][2];
                    }
                    for (int s = 0; s < (1 << 7); s++){
                        for (int k = 0; k < 7; k++){
                            if (y & (1 << k)){
                                swap(dp0[s][k][0], dp0[s][k][1]);
                            }
                            dp1[s ^ x][k][0] = add(dp1[s ^ x][k][0], dp0[s][k][0]);
                            dp1[s ^ x][k][1] = add(dp1[s ^ x][k][1], dp0[s][k][1]);
                        }
                    }
                    dp1.swap(dp0);
                }
                int segcnt = mul(i, n - j + 1);
                int t = mul(segcnt, 1 + (i != j));
                for (int s = 0; s < (1 << 7); s++){
                    for (int k = 0; k < 7; k++){
                        res = add(res, mul(mul(s, mul(dp0[s][k][1], (1 << k))), t));
                    }
                }
                // for (int mask = 0; mask < (1 << q); mask++){
                //     int x = a[i];
                //     int y = a[j];
                //     for (int k = 0; k < q; k++){
                //         if (mask & (1 << k)){
                //             if (req[k][0] <= i && i <= req[k][1]){
                //                 x ^= req[k][2];
                //             }
                //             if (req[k][0] <= j && j <= req[k][1]){
                //                 y ^= req[k][2];
                //             }
                //         }
                //     }
                //     int segcnt = mul(i, n - j + 1);
                //     res = add(res, mul(mul(2, segcnt), mul(x, y)));
                // }
            }
        }
        cout << res << "\n";
    }
    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 13 ms 420 KB Output is correct
4 Correct 11 ms 340 KB Output is correct
5 Correct 11 ms 340 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 13 ms 420 KB Output is correct
4 Correct 11 ms 340 KB Output is correct
5 Correct 11 ms 340 KB Output is correct
6 Correct 930 ms 408 KB Output is correct
7 Correct 906 ms 404 KB Output is correct
8 Correct 914 ms 400 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2059 ms 5844 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 2081 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 404 KB Output is correct
2 Correct 131 ms 404 KB Output is correct
3 Correct 129 ms 408 KB Output is correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 404 KB Output is correct
2 Correct 131 ms 404 KB Output is correct
3 Correct 129 ms 408 KB Output is correct
4 Execution timed out 2078 ms 596 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 13 ms 420 KB Output is correct
4 Correct 11 ms 340 KB Output is correct
5 Correct 11 ms 340 KB Output is correct
6 Correct 930 ms 408 KB Output is correct
7 Correct 906 ms 404 KB Output is correct
8 Correct 914 ms 400 KB Output is correct
9 Correct 129 ms 404 KB Output is correct
10 Correct 131 ms 404 KB Output is correct
11 Correct 129 ms 408 KB Output is correct
12 Execution timed out 2086 ms 340 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 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 13 ms 420 KB Output is correct
4 Correct 11 ms 340 KB Output is correct
5 Correct 11 ms 340 KB Output is correct
6 Correct 930 ms 408 KB Output is correct
7 Correct 906 ms 404 KB Output is correct
8 Correct 914 ms 400 KB Output is correct
9 Correct 129 ms 404 KB Output is correct
10 Correct 131 ms 404 KB Output is correct
11 Correct 129 ms 408 KB Output is correct
12 Execution timed out 2078 ms 596 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 13 ms 420 KB Output is correct
4 Correct 11 ms 340 KB Output is correct
5 Correct 11 ms 340 KB Output is correct
6 Correct 930 ms 408 KB Output is correct
7 Correct 906 ms 404 KB Output is correct
8 Correct 914 ms 400 KB Output is correct
9 Execution timed out 2059 ms 5844 KB Time limit exceeded
10 Halted 0 ms 0 KB -