oj.uz

Submission #830926

# Submission time Handle Problem Language Result Execution time Memory
830926 2023-08-19T13:00:08 Z rainboy Party (INOI20_party) C
7 / 100
 310 ms 340 KB 
#include <stdio.h>
#include <string.h>

#define N	200
#define MD	1000000007

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

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, h, i, j, s, d, ans;

		scanf("%lld", &n);
		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;
		}
		printf("%lld\n", (long long) ans * inv(pp2[n] - 1) % MD);
	}
	return 0;
}

Compilation message

Main.c: In function 'main':
Main.c:14:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
Main.c:20:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |   scanf("%lld", &n);
      |   ^~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 212 KB Output is correct
2 Correct 5 ms 212 KB Output is correct
3 Correct 4 ms 300 KB Output is correct
4 Correct 4 ms 212 KB Output is correct
5 Correct 7 ms 292 KB Output is correct
6 Correct 5 ms 212 KB Output is correct
7 Correct 7 ms 340 KB Output is correct
8 Correct 7 ms 212 KB Output is correct
9 Correct 6 ms 212 KB Output is correct
10 Correct 7 ms 212 KB Output is correct
11 Correct 310 ms 288 KB Output is correct
12 Correct 309 ms 292 KB Output is correct
13 Correct 307 ms 296 KB Output is correct
14 Correct 302 ms 212 KB Output is correct
15 Correct 307 ms 332 KB Output is correct
16 Correct 303 ms 296 KB Output is correct
17 Correct 171 ms 292 KB Output is correct
18 Correct 176 ms 288 KB Output is correct
19 Correct 173 ms 280 KB Output is correct
20 Correct 172 ms 296 KB Output is correct

Subtask #2
0 / 23.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 #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 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 5 ms 212 KB Output is correct
2 Correct 5 ms 212 KB Output is correct
3 Correct 4 ms 300 KB Output is correct
4 Correct 4 ms 212 KB Output is correct
5 Correct 7 ms 292 KB Output is correct
6 Correct 5 ms 212 KB Output is correct
7 Correct 7 ms 340 KB Output is correct
8 Correct 7 ms 212 KB Output is correct
9 Correct 6 ms 212 KB Output is correct
10 Correct 7 ms 212 KB Output is correct
11 Correct 310 ms 288 KB Output is correct
12 Correct 309 ms 292 KB Output is correct
13 Correct 307 ms 296 KB Output is correct
14 Correct 302 ms 212 KB Output is correct
15 Correct 307 ms 332 KB Output is correct
16 Correct 303 ms 296 KB Output is correct
17 Correct 171 ms 292 KB Output is correct
18 Correct 176 ms 288 KB Output is correct
19 Correct 173 ms 280 KB Output is correct
20 Correct 172 ms 296 KB Output is correct
21 Runtime error 1 ms 340 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -