Submission #564550

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
564550	2022-05-19T10:54:38 Z	Stickfish	Intergalactic ship (IZhO19_xorsum)	C++17	92 / 100	2000 ms	4108 KB

xorsum

#include <iostream>
#include <vector>
#include <map>
#include <bitset>
using namespace std;
using ll = long long;
using ull = unsigned long long;

const int MAXN = 1008;
const ll MOD = 1000000007;
const int MAXVAL = 128;
const int HEY = MAXVAL * 3;
int a[MAXN];

void updt(bitset<MAXVAL>& bs, int t) {
    if (bs[bs._Find_first() ^ t])
        return;
    bitset<MAXVAL> bs0;
    for (int i = bs._Find_first(); i < MAXVAL; i = bs._Find_next(i)) {
        bs0[i ^ t] = bs[i];
    }
    bs |= bs0;
}

ll pw(ll a, ll m) {
    if (!m)
        return 1;
    a %= MOD;
    if (m % 2)
        return a * pw(a, m - 1) % MOD;
    return pw(a * a, m / 2);
}

bool in(pair<int, int> sg, int i) {
    return sg.first <= i && i < sg.second;
}

vector<pair<int, int>> events[MAXN];
int change_ij[MAXN][MAXVAL];
int change_i[MAXN][MAXVAL];
int change_j[MAXN][MAXVAL];

struct sixple {
    ull first;
    ull second;
    ull third;
    ull fourth;
    ull fifth;
    ull sixth;

    bool operator<(sixple& s) {
        if (first != s.first)
            return first < s.first;
        if (second != s.second)
            return second < s.second;
        if (third != s.third)
            return third < s.third;
        if (fourth != s.fourth)
            return fourth < s.fourth;
        if (fifth != s.fifth)
            return fifth < s.fifth;
        return sixth < s.sixth;
    }
};

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    int q;
    cin >> q;
    for (int i = 0; i < q; ++i) {
        int l, r, x;
        cin >> l >> r >> x;
        --l;
        events[l].push_back({r, x});
        events[r].push_back({l, x});
        ++change_j[l][x];
        --change_j[r][x];
    }
    ll ans = 0;
    vector<int> genij0(MAXVAL, 0);
    bitset<MAXVAL> genbsij0;
    for (int i = 0; i < n; ++i) {
        for (auto [e, x] : events[i]) {
            if (e < i)
                genbsij0[x] = --genij0[x];
            else {
                genbsij0[x] = ++genij0[x];
                --change_ij[e][x];
                ++change_j[e][x];
                ++change_i[e][x];
            }
        }
        vector<int> geni(MAXVAL);
        bitset<MAXVAL> genbsi;
        vector<int> genj(MAXVAL);
        bitset<MAXVAL> genbsj;
        vector<int> genij = genij0;
        bitset<MAXVAL> genbsij = genbsij0;

        for (int j = i; j < n; ++j) {
            if (j > i) {
                for (int x = 0; x < 128; ++x) {
                    genbsij[x] = (genij[x] += change_ij[j][x]);
                    genbsi[x] = (geni[x] += change_i[j][x]);
                    genbsj[x] = (genj[x] += change_j[j][x]);
                }
            }
            bitset<MAXVAL> bsi;
            bitset<MAXVAL> bsj;
            bitset<MAXVAL> bsij;
            bsi[a[i]] = bsj[a[j]] = bsij[0] = 1;
            for (int xi = genbsi._Find_first(); xi < MAXVAL; xi = genbsi._Find_next(xi)) {
                updt(bsi, xi);
            }
            for (int xj = genbsj._Find_first(); xj < MAXVAL; xj = genbsj._Find_next(xj)) {
                updt(bsj, xj);
            }
            for (int xij = genbsij._Find_first(); xij < MAXVAL; xij = genbsij._Find_next(xij)) {
                updt(bsij, xij);
            }
            ll addans = 0;
            if (bsij.count() == 128 && (bsi.count() == 128 || bsj.count() == 128)) {
                if (bsi.count() == 128) {
                    addans += 64ll * 127 * 64 * 127 * bsj.count();
                } else {
                    addans += 64ll * 127 * 64 * 127 * bsi.count();
                }
            } else {
                vector<int> xj_from_xij(MAXVAL);
                for (int xij = bsij._Find_first(); xij < MAXVAL; xij = bsij._Find_next(xij)) {
                    if (bsj.count() == 128) {
                        xj_from_xij[xij] = 64 * 127;
                    } else {
                        for (int xj = bsj._Find_first(); xj < MAXVAL; xj = bsj._Find_next(xj)) {
                            xj_from_xij[xij] += xj ^ xij;
                        }
                    }
                }
                for (int xij = bsij._Find_first(); xij < MAXVAL; xij = bsij._Find_next(xij)) {
                    if (bsi.count() == 128) {
                        addans += xj_from_xij[xij] * 64 * 127;
                    } else {
                        for (int xi = bsi._Find_first(); xi < MAXVAL; xi = bsi._Find_next(xi)) {
                            addans += xj_from_xij[xij] * (xi ^ xij);
                        }
                    }
                    addans %= MOD;
                }
            }
            if (i != j) {
                addans *= 2;
            }
            addans *= (i + 1) * (n - j);
            addans %= MOD;
            addans *= pw(2, q);
            addans %= MOD;
            //cout << bsi.count() << ' ' << bsj.count() << ' ' << bsij.count() << endl;
            addans *= pw(bsi.count() * bsj.count() * bsij.count(), MOD - 2);
            ans += addans;
            ans %= MOD;
            //cout << i << ' ' << j << ": " << ans - ans0 << endl;
        }
    }
    cout << ans << endl;
}

Subtask #1
4.0 / 4.0

#	Verdict	Memory	Grader output
1	Correct	340 KB	Output is correct
2	Correct	340 KB	Output is correct
3	Correct	340 KB	Output is correct
4	Correct	340 KB	Output is correct
5	Correct	340 KB	Output is correct

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	9 ms	340 KB	Output is correct
7	Correct	5 ms	340 KB	Output is correct
8	Correct	5 ms	340 KB	Output is correct

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	2528 KB	Output is correct
2	Correct	13 ms	724 KB	Output is correct
3	Correct	8 ms	480 KB	Output is correct
4	Correct	5 ms	596 KB	Output is correct

Subtask #4
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	449 ms	1812 KB	Output is correct
2	Correct	456 ms	1748 KB	Output is correct
3	Correct	439 ms	1396 KB	Output is correct
4	Correct	445 ms	848 KB	Output is correct

Subtask #5
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	340 KB	Output is correct
2	Correct	2 ms	340 KB	Output is correct
3	Correct	2 ms	340 KB	Output is correct

Subtask #6
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	340 KB	Output is correct
2	Correct	2 ms	340 KB	Output is correct
3	Correct	2 ms	340 KB	Output is correct
4	Correct	8 ms	596 KB	Output is correct
5	Correct	7 ms	576 KB	Output is correct
6	Correct	7 ms	580 KB	Output is correct
7	Correct	7 ms	580 KB	Output is correct

Subtask #7
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	9 ms	340 KB	Output is correct
7	Correct	5 ms	340 KB	Output is correct
8	Correct	5 ms	340 KB	Output is correct
9	Correct	2 ms	340 KB	Output is correct
10	Correct	2 ms	340 KB	Output is correct
11	Correct	2 ms	340 KB	Output is correct
12	Correct	23 ms	480 KB	Output is correct
13	Correct	25 ms	468 KB	Output is correct
14	Correct	14 ms	468 KB	Output is correct
15	Correct	50 ms	468 KB	Output is correct

Subtask #8
30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	9 ms	340 KB	Output is correct
7	Correct	5 ms	340 KB	Output is correct
8	Correct	5 ms	340 KB	Output is correct
9	Correct	2 ms	340 KB	Output is correct
10	Correct	2 ms	340 KB	Output is correct
11	Correct	2 ms	340 KB	Output is correct
12	Correct	8 ms	596 KB	Output is correct
13	Correct	7 ms	576 KB	Output is correct
14	Correct	7 ms	580 KB	Output is correct
15	Correct	7 ms	580 KB	Output is correct
16	Correct	23 ms	480 KB	Output is correct
17	Correct	25 ms	468 KB	Output is correct
18	Correct	14 ms	468 KB	Output is correct
19	Correct	50 ms	468 KB	Output is correct
20	Correct	775 ms	3360 KB	Output is correct
21	Correct	537 ms	3200 KB	Output is correct
22	Correct	549 ms	3372 KB	Output is correct

Subtask #9
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	9 ms	340 KB	Output is correct
7	Correct	5 ms	340 KB	Output is correct
8	Correct	5 ms	340 KB	Output is correct
9	Correct	31 ms	2528 KB	Output is correct
10	Correct	13 ms	724 KB	Output is correct
11	Correct	8 ms	480 KB	Output is correct
12	Correct	5 ms	596 KB	Output is correct
13	Correct	449 ms	1812 KB	Output is correct
14	Correct	456 ms	1748 KB	Output is correct
15	Correct	439 ms	1396 KB	Output is correct
16	Correct	445 ms	848 KB	Output is correct
17	Correct	2 ms	340 KB	Output is correct
18	Correct	2 ms	340 KB	Output is correct
19	Correct	2 ms	340 KB	Output is correct
20	Correct	8 ms	596 KB	Output is correct
21	Correct	7 ms	576 KB	Output is correct
22	Correct	7 ms	580 KB	Output is correct
23	Correct	7 ms	580 KB	Output is correct
24	Correct	23 ms	480 KB	Output is correct
25	Correct	25 ms	468 KB	Output is correct
26	Correct	14 ms	468 KB	Output is correct
27	Correct	50 ms	468 KB	Output is correct
28	Correct	775 ms	3360 KB	Output is correct
29	Correct	537 ms	3200 KB	Output is correct
30	Correct	549 ms	3372 KB	Output is correct
31	Execution timed out	2075 ms	4108 KB	Time limit exceeded
32	Halted	0 ms	0 KB	-

Submission #564550

Compilation message