Submission #530911

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
530911	2022-02-27T05:31:19 Z	abc864197532	Intergalactic ship (IZhO19_xorsum)	C++17	47 / 100	2000 ms	2504 KB

xorsum

#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define pii pair<int,int>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T i, U ...j) {
	cout << i << ' ', abc(j...);
}
template <typename T> void printv(T l, T r) {
	for (; l != r; ++l)
		cout << *l << " \n"[l + 1 == r];
}
#ifdef Doludu
#define test(x...) abc("[" + string(#x) + "]", x);
#define owo freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#else
#define test(x...) void(0)
#define owo ios::sync_with_stdio(false)
#endif
const int N = 1005, mod = 1e9 + 7, inv = (mod + 1) / 2, C = 128;

void trans (vector <lli> &dp, int x) {
	vector <lli> pre = dp;
	for (int i = 0; i < C; ++i) {
		dp[i ^ x] += pre[i];
		if (dp[i ^ x] >= mod)
			dp[i ^ x] -= mod;
	}
}

int main () {
	owo;
	int n, q;
	cin >> n;
	vector <int> a(n);
	for (int i = 0; i < n; ++i)
		cin >> a[i];
	cin >> q;
	vector <array <int, 3>> queries(q);
	for (int i = 0; i < q; ++i) {
		cin >> queries[i][0] >> queries[i][1] >> queries[i][2];
		--queries[i][0];
	}
	lli ans = 0;
	for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) {
		lli pre = 0;
		vector <lli> dp1(C, 0), dp2(C, 0), dp3(C, 0);
		dp1[a[i]] = 1, dp2[a[j]] = 1, dp3[0] = 1;
		lli pw = 1;
		for (auto [l, r, x] : queries) {
			bool inter1 = l <= i && i < r, inter2 = l <= j && j < r;
			if (inter1 && inter2) {
				trans(dp3, x);
			} else if (inter1) {
				trans(dp1, x);
			} else if (inter2) {
				trans(dp2, x);
			} else {
				pw = pw * 2 % mod;
			}
		}
		for (int i = 0; i < C; ++i) {
			lli A = 0, B = 0;
			for (int j = 0; j < C; ++j) {
				(A += dp1[i ^ j] * j) %= mod;
				(B += dp2[i ^ j] * j) %= mod;
			}
			(pre += A * B % mod * dp3[i]) %= mod;
		}
		int ni = i, nj = j;
		if (ni > nj)
			swap(ni, nj);
		(ans += pre * pw % mod * (ni + 1) % mod * (n - nj)) %= mod;
	}
	cout << ans << '\n';
}

Subtask #1
4.0 / 4.0

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

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	2 ms	204 KB	Output is correct
3	Correct	9 ms	312 KB	Output is correct
4	Correct	7 ms	204 KB	Output is correct
5	Correct	8 ms	204 KB	Output is correct
6	Correct	706 ms	308 KB	Output is correct
7	Correct	692 ms	312 KB	Output is correct
8	Correct	704 ms	292 KB	Output is correct

Subtask #3
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2058 ms	2228 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	2037 ms	316 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	69 ms	292 KB	Output is correct
2	Correct	65 ms	204 KB	Output is correct
3	Correct	70 ms	308 KB	Output is correct

Subtask #6
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	69 ms	292 KB	Output is correct
2	Correct	65 ms	204 KB	Output is correct
3	Correct	70 ms	308 KB	Output is correct
4	Correct	676 ms	332 KB	Output is correct
5	Correct	684 ms	396 KB	Output is correct
6	Correct	662 ms	404 KB	Output is correct
7	Correct	665 ms	400 KB	Output is correct

Subtask #7
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	2 ms	204 KB	Output is correct
3	Correct	9 ms	312 KB	Output is correct
4	Correct	7 ms	204 KB	Output is correct
5	Correct	8 ms	204 KB	Output is correct
6	Correct	706 ms	308 KB	Output is correct
7	Correct	692 ms	312 KB	Output is correct
8	Correct	704 ms	292 KB	Output is correct
9	Correct	69 ms	292 KB	Output is correct
10	Correct	65 ms	204 KB	Output is correct
11	Correct	70 ms	308 KB	Output is correct
12	Correct	1083 ms	308 KB	Output is correct
13	Correct	1067 ms	304 KB	Output is correct
14	Correct	774 ms	320 KB	Output is correct
15	Correct	1043 ms	316 KB	Output is correct

Subtask #8
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	2 ms	204 KB	Output is correct
3	Correct	9 ms	312 KB	Output is correct
4	Correct	7 ms	204 KB	Output is correct
5	Correct	8 ms	204 KB	Output is correct
6	Correct	706 ms	308 KB	Output is correct
7	Correct	692 ms	312 KB	Output is correct
8	Correct	704 ms	292 KB	Output is correct
9	Correct	69 ms	292 KB	Output is correct
10	Correct	65 ms	204 KB	Output is correct
11	Correct	70 ms	308 KB	Output is correct
12	Correct	676 ms	332 KB	Output is correct
13	Correct	684 ms	396 KB	Output is correct
14	Correct	662 ms	404 KB	Output is correct
15	Correct	665 ms	400 KB	Output is correct
16	Correct	1083 ms	308 KB	Output is correct
17	Correct	1067 ms	304 KB	Output is correct
18	Correct	774 ms	320 KB	Output is correct
19	Correct	1043 ms	316 KB	Output is correct
20	Execution timed out	2005 ms	2504 KB	Time limit exceeded
21	Halted	0 ms	0 KB	-

Subtask #9
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	2 ms	204 KB	Output is correct
3	Correct	9 ms	312 KB	Output is correct
4	Correct	7 ms	204 KB	Output is correct
5	Correct	8 ms	204 KB	Output is correct
6	Correct	706 ms	308 KB	Output is correct
7	Correct	692 ms	312 KB	Output is correct
8	Correct	704 ms	292 KB	Output is correct
9	Execution timed out	2058 ms	2228 KB	Time limit exceeded
10	Halted	0 ms	0 KB	-

Submission #530911

Compilation message