oj.uz

Submission #342326

# Submission time Handle Problem Language Result Execution time Memory
342326 2021-01-01T22:12:02 Z kekw Intergalactic ship (IZhO19_xorsum) C++17
17 / 100
 2000 ms 2284 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>

#define range(i, n) for (int i = 0; i < (n); ++i)
#define ar array
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()


typedef long long ll;
typedef long double ld;
using namespace std;

//using namespace __gnu_pbds;

const ll INF = 1e18 + 5;
const int INFi = 1e9;
const int maxN = 1e7 + 1500;
const int md2 = 998244353;
const int md = 1e9 + 7;


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

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

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

int binpow(int a, int b) {
    if (b <= 0) return 1;
    if (b % 2) return mul(a, binpow(a, b - 1));
    int m = binpow(a, b / 2);
    return mul(m, m);
}


int rev(int a) {
    return binpow(a, md - 2);
}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    range(i, n) cin >> a[i];
    int q;
    cin >> q;
    vector<ar<int, 3>> b(q);
    range(i, q) range(j, 3) cin >> b[i][j];
    int ans = 0;
    range(i, n) {
        range(b1, 8) {
            range(j, n) {
                range(b2, 8) {
                    vector<int> dp(4);
                    int start = 0;
                    if (a[i] & (1 << b1)) start ^= 1;
                    if (a[j] & (1 << b2)) start ^= 2;
                    dp[start] = 1;
                    range(w, q) {
                        auto dp2 = dp;
                        range(e, 4) {
                            int e2 = e;
                            if (b[w][0] - 1 <= i && i < b[w][1] && (b[w][2] & (1 << b1))) e2 ^= 1;
                            if (b[w][0] - 1 <= j && j < b[w][1] && (b[w][2] & (1 << b2))) e2 ^= 2;
                            dp2[e2] = add(dp2[e2], dp[e]);
                        }
                        swap(dp, dp2);
                    }
                    int l = min(i, j);
                    int r = max(i, j);
                    ans = add(ans, mul(mul(l + 1, n - r), mul(dp[3], mul(1 << b1, 1 << b2))));
                }
            }
        }
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(15) << fixed;
    int tests = 1;
    //cin >> tests;
    range(_, tests) {
        solve();
    }
    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 372 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 4 ms 364 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 3 ms 364 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 372 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 4 ms 364 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 3 ms 364 KB Output is correct
6 Correct 294 ms 364 KB Output is correct
7 Correct 265 ms 492 KB Output is correct
8 Correct 295 ms 364 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2073 ms 2284 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 2092 ms 364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 364 KB Output is correct
2 Correct 54 ms 364 KB Output is correct
3 Correct 53 ms 492 KB Output is correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 364 KB Output is correct
2 Correct 54 ms 364 KB Output is correct
3 Correct 53 ms 492 KB Output is correct
4 Execution timed out 2087 ms 492 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 372 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 4 ms 364 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 3 ms 364 KB Output is correct
6 Correct 294 ms 364 KB Output is correct
7 Correct 265 ms 492 KB Output is correct
8 Correct 295 ms 364 KB Output is correct
9 Correct 53 ms 364 KB Output is correct
10 Correct 54 ms 364 KB Output is correct
11 Correct 53 ms 492 KB Output is correct
12 Execution timed out 2083 ms 364 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 372 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 4 ms 364 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 3 ms 364 KB Output is correct
6 Correct 294 ms 364 KB Output is correct
7 Correct 265 ms 492 KB Output is correct
8 Correct 295 ms 364 KB Output is correct
9 Correct 53 ms 364 KB Output is correct
10 Correct 54 ms 364 KB Output is correct
11 Correct 53 ms 492 KB Output is correct
12 Execution timed out 2087 ms 492 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 372 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 4 ms 364 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 3 ms 364 KB Output is correct
6 Correct 294 ms 364 KB Output is correct
7 Correct 265 ms 492 KB Output is correct
8 Correct 295 ms 364 KB Output is correct
9 Execution timed out 2073 ms 2284 KB Time limit exceeded
10 Halted 0 ms 0 KB -