oj.uz

Submission #286974

# Submission time Handle Problem Language Result Execution time Memory
286974 2020-08-31T08:17:59 Z oolimry Intergalactic ship (IZhO19_xorsum) C++14
17 / 100
 2000 ms 3308 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
using namespace std;
typedef long long lint;
typedef pair<int,int> ii;

int arr[1005];
struct query{ int l, r, x; };

vector<query> queries;

bool in(int x, int bit){
	return ((x & (1 << bit)) != 0);
}

lint mod = 1000000007;
lint two[100005];
lint ans = 0;

lint odd(int N){
	if(N == 0) return 0;
	else return two[N-1];
}
lint even(int N){
	if(N == 0) return 1;
	else return two[N-1];
}
void fix(lint &x){
	x %= mod;
	if(x < 0) x += mod;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	lint n; cin >> n;
	for(int i = 1;i <= n;i++) cin >> arr[i];
	
	int Q; cin >> Q;
	for(int q = 0;q < Q;q++){
		queries.push_back({});
		query &QQ = queries.back();
		cin >> QQ.l >> QQ.r >> QQ.x;
	}
	
	two[0] = 1;
	for(int i = 1;i <= 100004;i++) two[i] = (two[i-1] * 2);

	for(lint a = 1;a <= n;a++){
		for(lint b = 1;b <= n;b++){
			for(int aBit = 0;aBit < 7;aBit++){
				for(int bBit = 0;bBit < 7;bBit++){
					lint none = 0;
					lint onlyA = 0;
					lint onlyB = 0;
					lint both = 0;
					for(query q : queries){
						bool A = false, B = false;
						int l = q.l, r = q.r, x = q.x;
						
						if(in(x, aBit) && l <= a && a <= r) A = true;
						if(in(x, bBit) && l <= b && b <= r) B = true;
						
						if(A && B) both++;
						else if(A) onlyA++;
						else if(B) onlyB++;
						else none++;
					}
					
					//cout << a << " " << b << " " << aBit << " " << bBit << ": " << none << " " << onlyA << " " << onlyB << " " << both << "\n";
					
					///don't use "both"
					lint res = two[none] * two[aBit + bBit];
					fix(res);
					res *= min(a,b) * (n - max(a,b) + 1);
					fix(res);
					
					
					if(in(arr[a], aBit)) res *= even(onlyA);
					else res *= odd(onlyA);
					fix(res);
					
					if(in(arr[b], bBit)) res *= even(onlyB);
					else res *= odd(onlyB);
					fix(res);
					
					res *= even(both);
					fix(res);
					
					
					ans += res;
					fix(ans);
					//cout << res << " ";
					
					
					///use "both"
					res = two[none] * two[aBit + bBit];
					fix(res);
					res *= min(a,b) * (n - max(a,b) + 1);
					fix(res);
					
					if(in(arr[a], aBit)) res *= odd(onlyA);
					else res *= even(onlyA);
					fix(res);
					
					if(in(arr[b], bBit)) res *= odd(onlyB);
					else res *= even(onlyB);
					fix(res);
					
					res *= odd(both);
					fix(res);
					
					ans += res;
					fix(ans);	
				}
			}
		} 
	}
	
	cout << ans << "\n";
}

Subtask #1
4.0 / 4.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1152 KB Output is correct
2 Correct 1 ms 1152 KB Output is correct
3 Correct 2 ms 1152 KB Output is correct
4 Correct 2 ms 1152 KB Output is correct
5 Correct 2 ms 1152 KB Output is correct
6 Correct 48 ms 1152 KB Output is correct
7 Correct 35 ms 1152 KB Output is correct
8 Correct 31 ms 1168 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2071 ms 3308 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 2079 ms 1152 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
8.0 / 8.0

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

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1152 KB Output is correct
2 Correct 8 ms 1152 KB Output is correct
3 Correct 8 ms 1152 KB Output is correct
4 Execution timed out 2033 ms 1280 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 1152 KB Output is correct
2 Correct 1 ms 1152 KB Output is correct
3 Correct 2 ms 1152 KB Output is correct
4 Correct 2 ms 1152 KB Output is correct
5 Correct 2 ms 1152 KB Output is correct
6 Correct 48 ms 1152 KB Output is correct
7 Correct 35 ms 1152 KB Output is correct
8 Correct 31 ms 1168 KB Output is correct
9 Correct 10 ms 1152 KB Output is correct
10 Correct 8 ms 1152 KB Output is correct
11 Correct 8 ms 1152 KB Output is correct
12 Incorrect 1674 ms 1188 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1152 KB Output is correct
2 Correct 1 ms 1152 KB Output is correct
3 Correct 2 ms 1152 KB Output is correct
4 Correct 2 ms 1152 KB Output is correct
5 Correct 2 ms 1152 KB Output is correct
6 Correct 48 ms 1152 KB Output is correct
7 Correct 35 ms 1152 KB Output is correct
8 Correct 31 ms 1168 KB Output is correct
9 Correct 10 ms 1152 KB Output is correct
10 Correct 8 ms 1152 KB Output is correct
11 Correct 8 ms 1152 KB Output is correct
12 Execution timed out 2033 ms 1280 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 1152 KB Output is correct
2 Correct 1 ms 1152 KB Output is correct
3 Correct 2 ms 1152 KB Output is correct
4 Correct 2 ms 1152 KB Output is correct
5 Correct 2 ms 1152 KB Output is correct
6 Correct 48 ms 1152 KB Output is correct
7 Correct 35 ms 1152 KB Output is correct
8 Correct 31 ms 1168 KB Output is correct
9 Execution timed out 2071 ms 3308 KB Time limit exceeded
10 Halted 0 ms 0 KB -