oj.uz

Submission #679466

# Submission time Handle Problem Language Result Execution time Memory
679466 2023-01-08T10:48:01 Z grandmast3r Intergalactic ship (IZhO19_xorsum) C++17
17 / 100
 2000 ms 5888 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];
            }
        }
        random_shuffle(all(req));
        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 11 ms 340 KB Output is correct
4 Correct 11 ms 340 KB Output is correct
5 Correct 13 ms 316 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 11 ms 340 KB Output is correct
4 Correct 11 ms 340 KB Output is correct
5 Correct 13 ms 316 KB Output is correct
6 Correct 940 ms 408 KB Output is correct
7 Correct 914 ms 404 KB Output is correct
8 Correct 951 ms 408 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2084 ms 5888 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 2078 ms 468 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 400 KB Output is correct
2 Correct 131 ms 404 KB Output is correct
3 Correct 150 ms 404 KB Output is correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 400 KB Output is correct
2 Correct 131 ms 404 KB Output is correct
3 Correct 150 ms 404 KB Output is correct
4 Execution timed out 2085 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 11 ms 340 KB Output is correct
4 Correct 11 ms 340 KB Output is correct
5 Correct 13 ms 316 KB Output is correct
6 Correct 940 ms 408 KB Output is correct
7 Correct 914 ms 404 KB Output is correct
8 Correct 951 ms 408 KB Output is correct
9 Correct 137 ms 400 KB Output is correct
10 Correct 131 ms 404 KB Output is correct
11 Correct 150 ms 404 KB Output is correct
12 Execution timed out 2071 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 11 ms 340 KB Output is correct
4 Correct 11 ms 340 KB Output is correct
5 Correct 13 ms 316 KB Output is correct
6 Correct 940 ms 408 KB Output is correct
7 Correct 914 ms 404 KB Output is correct
8 Correct 951 ms 408 KB Output is correct
9 Correct 137 ms 400 KB Output is correct
10 Correct 131 ms 404 KB Output is correct
11 Correct 150 ms 404 KB Output is correct
12 Execution timed out 2085 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 11 ms 340 KB Output is correct
4 Correct 11 ms 340 KB Output is correct
5 Correct 13 ms 316 KB Output is correct
6 Correct 940 ms 408 KB Output is correct
7 Correct 914 ms 404 KB Output is correct
8 Correct 951 ms 408 KB Output is correct
9 Execution timed out 2084 ms 5888 KB Time limit exceeded
10 Halted 0 ms 0 KB -