oj.uz

Submission #830952

# Submission time Handle Problem Language Result Execution time Memory
830952 2023-08-19T13:32:26 Z rainboy Party (INOI20_party) C
30 / 100
 2403 ms 568 KB 
#include <stdio.h>
#include <string.h>

#define N	200
#define MD	1000000007

int min(int a, int b) { return a < b ? a : b; }

int inv(int a) {
	return a == 1 ? 1 : (long long) inv(a - MD % a) * (MD / a + 1) % MD;
}

long long count(int d) {
	return (1LL << (d + 1) / 2) + (1LL << (d + 2) / 2) - 2;
}

long long power(long long a, long long k) {
	long long p = 1;

	while (k) {
		if (k & 1)
			p = p * a % MD;
		a = a * a % MD;
		k >>= 1;
	}
	return p;
}

int main() {
	int q;

	scanf("%d", &q);
	while (q--) {
		static int pp2[N + 1], dd[N + 1], qu[N], kk[N];
		long long n, k;
		int cnt, l, h, i, j, s, d, ans;

		scanf("%lld", &n);
		if ((n & n + 1) == 0) {
			l = 0;
			while (1LL << l + 1 <= n)
				l++;
			ans = 0;
			for (i = 0; i <= l; i++)
				for (d = 0; d <= l * 2; d++) {
					k = count(d + min(d, l - i));
					if (d > i)
						k += (1LL << min(d - i, l) + 1) - 1 - count(d - i + min(d - i, l));
					ans = (ans + (power(2, n - k) - 1) * ((1LL << i) % MD)) % MD;
				}
		} else {
			pp2[0] = 1;
			for (i = 1; i <= n; i++)
				pp2[i] = pp2[i - 1] * 2 % MD;
			ans = 0;
			for (s = 1; s <= n; s++) {
				for (i = 1; i <= n; i++)
					dd[i] = n;
				cnt = 0;
				dd[s] = 0, qu[cnt++] = s;
				for (h = 0; h < cnt; h++) {
					i = qu[h], d = dd[i] + 1;
					if ((j = i >> 1) > 0 && dd[j] > d)
						dd[j] = d, qu[cnt++] = j;
					if ((j = i << 1 | 0) <= n && dd[j] > d)
						dd[j] = d, qu[cnt++] = j;
					if ((j = i << 1 | 1) <= n && dd[j] > d)
						dd[j] = d, qu[cnt++] = j;
				}
				memset(kk, 0, n * sizeof *kk);
				for (i = 1; i <= n; i++)
					kk[dd[i]]++;
				for (d = 1; d < n; d++)
					kk[d] += kk[d - 1];
				for (d = 0; d < n; d++)
					ans = (ans + pp2[n - kk[d]] - 1) % MD;
			}
		}
		ans = (long long) ans * inv(power(2, n) - 1) % MD;
		printf("%d\n", ans);
	}
	return 0;
}

Compilation message

Main.c: In function 'main':
Main.c:39:14: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   39 |   if ((n & n + 1) == 0) {
      |            ~~^~~
Main.c:41:20: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   41 |    while (1LL << l + 1 <= n)
      |                  ~~^~~
Main.c:48:34: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   48 |       k += (1LL << min(d - i, l) + 1) - 1 - count(d - i + min(d - i, l));
      |                    ~~~~~~~~~~~~~~^~~
Main.c:32:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
Main.c:38:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |   scanf("%lld", &n);
      |   ^~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 212 KB Output is correct
2 Correct 5 ms 212 KB Output is correct
3 Correct 4 ms 212 KB Output is correct
4 Correct 9 ms 280 KB Output is correct
5 Correct 7 ms 212 KB Output is correct
6 Correct 5 ms 284 KB Output is correct
7 Correct 6 ms 212 KB Output is correct
8 Correct 7 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 4 ms 212 KB Output is correct
12 Correct 4 ms 212 KB Output is correct
13 Correct 312 ms 264 KB Output is correct
14 Correct 317 ms 392 KB Output is correct
15 Correct 312 ms 280 KB Output is correct
16 Correct 313 ms 280 KB Output is correct
17 Correct 182 ms 276 KB Output is correct
18 Correct 181 ms 280 KB Output is correct
19 Correct 179 ms 268 KB Output is correct
20 Correct 182 ms 268 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 212 KB Output is correct
2 Correct 71 ms 212 KB Output is correct
3 Correct 63 ms 276 KB Output is correct
4 Correct 55 ms 272 KB Output is correct
5 Correct 66 ms 292 KB Output is correct
6 Correct 64 ms 212 KB Output is correct
7 Correct 59 ms 288 KB Output is correct
8 Correct 62 ms 212 KB Output is correct
9 Correct 59 ms 212 KB Output is correct
10 Correct 63 ms 212 KB Output is correct
11 Correct 2399 ms 312 KB Output is correct
12 Correct 2397 ms 568 KB Output is correct
13 Correct 2403 ms 436 KB Output is correct
14 Correct 2402 ms 320 KB Output is correct
15 Correct 2396 ms 320 KB Output is correct
16 Correct 2398 ms 328 KB Output is correct
17 Correct 2398 ms 444 KB Output is correct
18 Correct 2397 ms 460 KB Output is correct
19 Correct 2397 ms 324 KB Output is correct
20 Correct 2400 ms 324 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 212 KB Output is correct
2 Correct 5 ms 212 KB Output is correct
3 Correct 4 ms 212 KB Output is correct
4 Correct 9 ms 280 KB Output is correct
5 Correct 7 ms 212 KB Output is correct
6 Correct 5 ms 284 KB Output is correct
7 Correct 6 ms 212 KB Output is correct
8 Correct 7 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 4 ms 212 KB Output is correct
12 Correct 4 ms 212 KB Output is correct
13 Correct 312 ms 264 KB Output is correct
14 Correct 317 ms 392 KB Output is correct
15 Correct 312 ms 280 KB Output is correct
16 Correct 313 ms 280 KB Output is correct
17 Correct 182 ms 276 KB Output is correct
18 Correct 181 ms 280 KB Output is correct
19 Correct 179 ms 268 KB Output is correct
20 Correct 182 ms 268 KB Output is correct
21 Correct 61 ms 212 KB Output is correct
22 Correct 71 ms 212 KB Output is correct
23 Correct 63 ms 276 KB Output is correct
24 Correct 55 ms 272 KB Output is correct
25 Correct 66 ms 292 KB Output is correct
26 Correct 64 ms 212 KB Output is correct
27 Correct 59 ms 288 KB Output is correct
28 Correct 62 ms 212 KB Output is correct
29 Correct 59 ms 212 KB Output is correct
30 Correct 63 ms 212 KB Output is correct
31 Correct 2399 ms 312 KB Output is correct
32 Correct 2397 ms 568 KB Output is correct
33 Correct 2403 ms 436 KB Output is correct
34 Correct 2402 ms 320 KB Output is correct
35 Correct 2396 ms 320 KB Output is correct
36 Correct 2398 ms 328 KB Output is correct
37 Correct 2398 ms 444 KB Output is correct
38 Correct 2397 ms 460 KB Output is correct
39 Correct 2397 ms 324 KB Output is correct
40 Correct 2400 ms 324 KB Output is correct
41 Runtime error 1 ms 340 KB Execution killed with signal 11
42 Halted 0 ms 0 KB -