oj.uz

Submission #679457

# Submission time Handle Problem Language Result Execution time Memory
679457 2023-01-08T10:01:53 Z grandmast3r Intergalactic ship (IZhO19_xorsum) C++17
17 / 100
 2000 ms 5784 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 + 1; 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);
                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))), mul(segcnt, 2)));
                    }
                }
                // 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 1 ms 340 KB Output is correct
3 Correct 10 ms 444 KB Output is correct
4 Correct 9 ms 340 KB Output is correct
5 Correct 9 ms 424 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 1 ms 340 KB Output is correct
3 Correct 10 ms 444 KB Output is correct
4 Correct 9 ms 340 KB Output is correct
5 Correct 9 ms 424 KB Output is correct
6 Correct 916 ms 400 KB Output is correct
7 Correct 887 ms 460 KB Output is correct
8 Correct 887 ms 424 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2096 ms 5784 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 2090 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 1915 ms 292 KB Output is correct
2 Correct 1948 ms 412 KB Output is correct
3 Correct 1892 ms 296 KB Output is correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1915 ms 292 KB Output is correct
2 Correct 1948 ms 412 KB Output is correct
3 Correct 1892 ms 296 KB Output is correct
4 Execution timed out 2065 ms 612 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 1 ms 340 KB Output is correct
3 Correct 10 ms 444 KB Output is correct
4 Correct 9 ms 340 KB Output is correct
5 Correct 9 ms 424 KB Output is correct
6 Correct 916 ms 400 KB Output is correct
7 Correct 887 ms 460 KB Output is correct
8 Correct 887 ms 424 KB Output is correct
9 Correct 1915 ms 292 KB Output is correct
10 Correct 1948 ms 412 KB Output is correct
11 Correct 1892 ms 296 KB Output is correct
12 Execution timed out 2097 ms 320 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 1 ms 340 KB Output is correct
3 Correct 10 ms 444 KB Output is correct
4 Correct 9 ms 340 KB Output is correct
5 Correct 9 ms 424 KB Output is correct
6 Correct 916 ms 400 KB Output is correct
7 Correct 887 ms 460 KB Output is correct
8 Correct 887 ms 424 KB Output is correct
9 Correct 1915 ms 292 KB Output is correct
10 Correct 1948 ms 412 KB Output is correct
11 Correct 1892 ms 296 KB Output is correct
12 Execution timed out 2065 ms 612 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 1 ms 340 KB Output is correct
3 Correct 10 ms 444 KB Output is correct
4 Correct 9 ms 340 KB Output is correct
5 Correct 9 ms 424 KB Output is correct
6 Correct 916 ms 400 KB Output is correct
7 Correct 887 ms 460 KB Output is correct
8 Correct 887 ms 424 KB Output is correct
9 Execution timed out 2096 ms 5784 KB Time limit exceeded
10 Halted 0 ms 0 KB -