oj.uz

Submission #830948

# Submission time Handle Problem Language Result Execution time Memory
830948 2023-08-19T13:30:57 Z rainboy Party (INOI20_party) C
7 / 100
 3000 ms 404 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, int 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 212 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 9 ms 288 KB Output is correct
6 Correct 6 ms 212 KB Output is correct
7 Correct 6 ms 284 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 284 KB Output is correct
12 Correct 4 ms 212 KB Output is correct
13 Correct 310 ms 276 KB Output is correct
14 Correct 308 ms 272 KB Output is correct
15 Correct 319 ms 280 KB Output is correct
16 Correct 310 ms 284 KB Output is correct
17 Correct 180 ms 404 KB Output is correct
18 Correct 176 ms 280 KB Output is correct
19 Correct 183 ms 280 KB Output is correct
20 Correct 179 ms 268 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3057 ms 212 KB Time limit exceeded
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 212 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 9 ms 288 KB Output is correct
6 Correct 6 ms 212 KB Output is correct
7 Correct 6 ms 284 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 284 KB Output is correct
12 Correct 4 ms 212 KB Output is correct
13 Correct 310 ms 276 KB Output is correct
14 Correct 308 ms 272 KB Output is correct
15 Correct 319 ms 280 KB Output is correct
16 Correct 310 ms 284 KB Output is correct
17 Correct 180 ms 404 KB Output is correct
18 Correct 176 ms 280 KB Output is correct
19 Correct 183 ms 280 KB Output is correct
20 Correct 179 ms 268 KB Output is correct
21 Execution timed out 3057 ms 212 KB Time limit exceeded
22 Halted 0 ms 0 KB -