Submission #1004910

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1004910	2024-06-22T03:03:06 Z	pavement	Flooding Wall (BOI24_wall)	C++17	0 / 100	5000 ms	604 KB

Main

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define pb push_back

const int MOD = (int)1e9 + 7, INV_2 = (MOD + 1) / 2;
int N, glob, a[500005], b[500005];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= N; i++) {
		cin >> b[i];
		if (a[i] > b[i]) {
			swap(a[i], b[i]);
		}
	}
	for (int i = 1; i <= N; i++) {
		for (int h : {a[i], b[i]}) {
			int expected = 0;
			vector<int> probs = {1};
			for (int v = h + 1; v <= 1000; v++) {
				int lft_prob = 1, rig_prob = 1;
				for (int j = 1; j < i; j++) {
					int cur_prob = INV_2;
					if (a[j] >= v) {
						cur_prob = 0;
					} else if (b[j] < v) {
						cur_prob = 1;
					}
					lft_prob = ((ll)lft_prob * cur_prob) % MOD;
				}
				lft_prob = (1 - lft_prob + MOD) % MOD;
				for (int j = i + 1; j <= N; j++) {
					int cur_prob = INV_2;
					if (a[j] >= v) {
						cur_prob = 0;
					} else if (b[j] < v) {
						cur_prob = 1;
					}
					rig_prob = ((ll)rig_prob * cur_prob) % MOD;
				}
				rig_prob = (1 - rig_prob + MOD) % MOD;
				int p = (ll)lft_prob * rig_prob % MOD;
				probs.pb(p);
			}
			for (int v = 0; v + 1 < (int)probs.size(); v++) {
				int tmp = (probs[v] - probs[v + 1] + MOD) % MOD;
				if (tmp == 0) {
					continue;
				}
				expected = (expected + (ll)(v + h) * tmp % MOD) % MOD;
			}
			expected = (expected - h + MOD) % MOD;
			glob = (glob + expected) % MOD;
		}
	}
	for (int rep = 0; rep < N - 1; rep++) {
		glob = (glob * 2) % MOD;
	}
	cout << glob << '\n';
}

Subtask #1

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	468 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Incorrect	0 ms	348 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #2

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	468 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	2 ms	348 KB	Output is correct
12	Correct	1 ms	344 KB	Output is correct
13	Correct	2 ms	344 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	23 ms	348 KB	Output is correct
16	Incorrect	22 ms	348 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #3

0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	468 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	2 ms	348 KB	Output is correct
12	Correct	1 ms	344 KB	Output is correct
13	Correct	2 ms	344 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	23 ms	348 KB	Output is correct
16	Incorrect	22 ms	348 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #4

0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	468 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Incorrect	0 ms	348 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #5

0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	468 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	604 KB	Output is correct
6	Correct	2 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	57 ms	348 KB	Output is correct
9	Correct	53 ms	456 KB	Output is correct
10	Execution timed out	5092 ms	600 KB	Time limit exceeded
11	Halted	0 ms	0 KB	-

Subtask #6

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	468 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Incorrect	0 ms	348 KB	Output isn't correct
12	Halted	0 ms	0 KB	-