oj.uz

Submission #830951

# Submission time Handle Problem Language Result Execution time Memory
830951 2023-08-19T13:31:52 Z rainboy Party (INOI20_party) C
7 / 100
 318 ms 340 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;
		int cnt, l, h, i, j, k, 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 284 KB Output is correct
2 Correct 5 ms 212 KB Output is correct
3 Correct 5 ms 212 KB Output is correct
4 Correct 4 ms 212 KB Output is correct
5 Correct 7 ms 212 KB Output is correct
6 Correct 6 ms 212 KB Output is correct
7 Correct 6 ms 212 KB Output is correct
8 Correct 7 ms 288 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 5 ms 212 KB Output is correct
13 Correct 318 ms 276 KB Output is correct
14 Correct 312 ms 276 KB Output is correct
15 Correct 317 ms 280 KB Output is correct
16 Correct 313 ms 212 KB Output is correct
17 Correct 180 ms 280 KB Output is correct
18 Correct 179 ms 212 KB Output is correct
19 Correct 179 ms 276 KB Output is correct
20 Correct 180 ms 280 KB Output is correct

Subtask #2
0 / 23.0

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

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 284 KB Output is correct
2 Correct 5 ms 212 KB Output is correct
3 Correct 5 ms 212 KB Output is correct
4 Correct 4 ms 212 KB Output is correct
5 Correct 7 ms 212 KB Output is correct
6 Correct 6 ms 212 KB Output is correct
7 Correct 6 ms 212 KB Output is correct
8 Correct 7 ms 288 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 5 ms 212 KB Output is correct
13 Correct 318 ms 276 KB Output is correct
14 Correct 312 ms 276 KB Output is correct
15 Correct 317 ms 280 KB Output is correct
16 Correct 313 ms 212 KB Output is correct
17 Correct 180 ms 280 KB Output is correct
18 Correct 179 ms 212 KB Output is correct
19 Correct 179 ms 276 KB Output is correct
20 Correct 180 ms 280 KB Output is correct
21 Incorrect 78 ms 212 KB Output isn't correct
22 Halted 0 ms 0 KB -