oj.uz

답안 #679457

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2096 ms 5784 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -