oj.uz

Submission #227523

# Submission time Handle Problem Language Result Execution time Memory
227523 2020-04-27T16:25:27 Z srvlt Intergalactic ship (IZhO19_xorsum) C++14
9 / 100
 200 ms 262148 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define db long double
#define pb push_back
#define ppb pop_back
#define F first
#define S second
#define mp make_pair
#define all(x) (x).begin(), (x).end()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int N = 1003, M = 100003, K = 128, MOD = 1e9 + 7;
int n, q, a[N], pw[M];
vector <pii> L[N], R[N];

int bit[K], mask[K];

struct basis {
	vector <int> b;
	int sz = 0;
	bitset <K> can;
	basis() {
		can[0] = 1;
	}
	void clear() {
		sz = 0;
		b.clear();
		can.reset();
		can[0] = 1;
	}
	void upd() {
		int bsz = b.size();
		can.reset();
		for (int i = 0; i < (1 << bsz); i++) {
			if (i > 0) {
				mask[i] = mask[i ^ (1 << bit[i])] ^ b[bit[i]];
			}
			can[mask[i]] = 1;
		}
	}
	bool add(int x) {
		sz++;
		if (can[x]) {
			return false;
		}
		for (int i : b) {
			x = min(x, x ^ i);
		}
		b.pb(x);
		upd();
		return true;
	}
	int ways() {
		return pw[sz - (int)b.size()];
	}
};

basis cur, C[N][N], A[N][N];
int f[K][N][N], g[K];
int last[N][N];

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	#ifdef LOCAL
		freopen("input.txt", "r", stdin);
	#endif
	
	pw[0] = 1;
	for (int i = 1; i < M; i++) {
		pw[i] = (ll)pw[i - 1] * 2 % M;
	}
	
	for (int i = 1; i < K; i++) {
		for (int j = 6; j >= 0; j--) {
			if (i >> j & 1) {
				bit[i] = j;
				break;
			}
		}
	}
	
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	cin >> q;
	for (int i = 1; i <= q; i++) {
		int l, r, x;
		cin >> l >> r >> x;
		R[r].pb({l, x});
		L[l].pb({r, x});
	}
	for (int l = 1; l <= n; l++) {
		cur.clear();
		for (int r = n; r >= l; r--) {
			for (auto i : R[r]) {
				if (i.F <= l) {
					cur.add(i.S);
				}
			}
			C[l][r] = cur;
		}
	}
	for (int l = 1; l <= n; l++) {
		cur.clear();
		last[l][l] = l;
		for (int r = l; r <= n; r++) {
			if (last[l][r] == r) {
				A[l][r] = cur;
				for (int i = 0; i < K; i++) {
					for (int j = 0; j < K; j++) {
						f[i][l][r] += j * cur.can[j ^ i];
						if (f[i][l][r] >= MOD) {
							f[i][l][r] -= MOD;
						}
					}
				}
			}	else {
				last[l][r] = last[l][r - 1];
			}
			for (auto i : R[r]) {
				if (i.F <= l && cur.add(i.S)) {
					last[l][r + 1] = r + 1;
				}
			}
		}
	}
	int ans = 0;
	for (int r = n; r >= 1; r--) {
		cur.clear();
		for (int i = 0; i < K; i++) {
			g[i] = 0;
			for (int j = 0; j < K; j++) {
				g[i] += j * cur.can[j ^ i];
				if (g[i] >= MOD) {
					g[i] -= MOD;
				}
			}
		}
		for (int l = r; l >= 1; l--) {
			int res = 0, pos = last[l][r];
			for (int i = 0; i < K; i++) {
				res += ((ll)C[l][r].can[i] * f[i ^ a[l]][l][pos] % MOD) * g[i ^ a[r]] % MOD;
				if (res >= MOD) {
					res -= MOD;
				}
			}
			res = (ll)res * C[l][r].ways() % MOD;
			res = (ll)res * A[l][pos].ways() % MOD;
			res = (ll)res * cur.ways() % MOD;
			res = (ll)res * pw[q - C[l][r].sz - A[l][pos].sz - cur.sz] % MOD;
			if (l == r) {
				res = (ll)res * ((MOD + 1) / 2) % MOD;
			}
			int occ = l * (n - r + 1);
			ans += (ll)res * occ % MOD;
			if (ans >= MOD) {
				ans -= MOD;
			}
			for (auto i : L[l]) {
				if (i.F >= r && cur.add(i.S)) {
					for (int k = 0; k < K; k++) {
						g[k] = 0;
						for (int j = 0; j < K; j++) {
							g[k] += j * cur.can[j ^ k];
							if (g[k] >= MOD) {
								g[k] -= MOD;
							}
						}
					}
				}
			}
		}
	}
	cout << (ll)2 * ans % MOD;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 96888 KB Output is correct
2 Correct 61 ms 98424 KB Output is correct
3 Correct 70 ms 100860 KB Output is correct
4 Correct 67 ms 100856 KB Output is correct
5 Correct 76 ms 100832 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 96888 KB Output is correct
2 Correct 61 ms 98424 KB Output is correct
3 Correct 70 ms 100860 KB Output is correct
4 Correct 67 ms 100856 KB Output is correct
5 Correct 76 ms 100832 KB Output is correct
6 Correct 137 ms 146736 KB Output is correct
7 Correct 117 ms 146424 KB Output is correct
8 Correct 119 ms 146680 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 175 ms 148704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 200 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 84 ms 111096 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 84 ms 111096 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 96888 KB Output is correct
2 Correct 61 ms 98424 KB Output is correct
3 Correct 70 ms 100860 KB Output is correct
4 Correct 67 ms 100856 KB Output is correct
5 Correct 76 ms 100832 KB Output is correct
6 Correct 137 ms 146736 KB Output is correct
7 Correct 117 ms 146424 KB Output is correct
8 Correct 119 ms 146680 KB Output is correct
9 Incorrect 84 ms 111096 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 96888 KB Output is correct
2 Correct 61 ms 98424 KB Output is correct
3 Correct 70 ms 100860 KB Output is correct
4 Correct 67 ms 100856 KB Output is correct
5 Correct 76 ms 100832 KB Output is correct
6 Correct 137 ms 146736 KB Output is correct
7 Correct 117 ms 146424 KB Output is correct
8 Correct 119 ms 146680 KB Output is correct
9 Incorrect 84 ms 111096 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 96888 KB Output is correct
2 Correct 61 ms 98424 KB Output is correct
3 Correct 70 ms 100860 KB Output is correct
4 Correct 67 ms 100856 KB Output is correct
5 Correct 76 ms 100832 KB Output is correct
6 Correct 137 ms 146736 KB Output is correct
7 Correct 117 ms 146424 KB Output is correct
8 Correct 119 ms 146680 KB Output is correct
9 Incorrect 175 ms 148704 KB Output isn't correct
10 Halted 0 ms 0 KB -