oj.uz

Submission #1058859

# Submission time Handle Problem Language Result Execution time Memory
1058859 2024-08-14T14:34:39 Z rainboy COVID tests (CEOI24_covid) C
10 / 100
 5825 ms 11860 KB 
#include <stdio.h>
#include <string.h>

#define N	1000
#define INF	1e9

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

unsigned int Z = 12345;

int rand_() {
	return (Z *= 3) >> 1;
}

int n, m; double p;

int query(int l, int r) {
	static char cc[N + 1], s[2];

	memset(cc, '0', n * sizeof *cc), memset(cc + l, '1', (r - l) * sizeof *cc);
	printf("Q %s\n", cc), fflush(stdout);
	scanf("%s", s);
	return s[0] == 'P';
}

double qq[N + 1], dp[N + 1], dq[N + 1][N + 1]; int ll[N + 1], mm[N + 1][N + 1];

void init() {
	int i, l, r, m;
	double x;

	qq[0] = 1;
	for (i = 1; i <= n; i++)
		qq[i] = qq[i - 1] * (1 - p);
	dp[0] = 0;
	for (r = 1; r <= n; r++) {
		dp[r] = INF;
		for (l = r - 1; l >= 0 && l >= r - n / 2; l--) {
			if (r - l == 1)
				dq[l][r] = dp[l];
			else {
				dq[l][r] = INF;
				for (m = r - 1; m > l; m--) {
					x = (dq[l][m] * qq[r - m] * (1 - qq[m - l]) + dq[m][r] * (1 - qq[r - l] - qq[r - m] * (1 - qq[m - l]))) / (1 - qq[r - l]) + 1;
					if (dq[l][r] > x)
						dq[l][r] = x, mm[l][r] = m;
				}
			}
			x = dp[l] * qq[r - l] + dq[l][r] * (1 - qq[r - l]) + 1;
			if (dp[r] > x)
				dp[r] = x, ll[r] = l;
		}
	}
}

char cc[N + 1];

void solve(int r);

void solve_(int l, int r) {
	if (r - l == 1)
		cc[l] = '1', solve(l);
	else if (query(mm[l][r], r))
		solve_(mm[l][r], r);
	else
		solve_(l, mm[l][r]);
}

void solve(int r) {
	if (query(ll[r], r))
		solve_(ll[r], r);
	else
		solve(ll[r]);
}

int main() {
	int t, subtask;

	scanf("%d%lf%d", &n, &p, &t), m = 1 / p * 4, subtask = t == 1 ? 1 : 2, init();
	while (t--) {
		int i;

		memset(cc, '0', n * sizeof *cc), cc[n] = 0;
		if (subtask == 1) {
			for (i = 0; i < n; i++)
				if (query(i, i + 1))
					cc[i] = '1';
		} else
			solve(n);
		printf("A %s\n", cc), fflush(stdout);
		scanf("%*s");
	}
	return 0;
}

Compilation message

Main.c: In function 'query':
Main.c:22:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |  scanf("%s", s);
      |  ^~~~~~~~~~~~~~
Main.c: In function 'main':
Main.c:79:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |  scanf("%d%lf%d", &n, &p, &t), m = 1 / p * 4, subtask = t == 1 ? 1 : 2, init();
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.c:91:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |   scanf("%*s");
      |   ^~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5825 ms 2392 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 11856 KB Output is correct
2 Correct 124 ms 11856 KB Output is correct
3 Correct 127 ms 11856 KB Output is correct
4 Correct 127 ms 11856 KB Output is correct
5 Correct 123 ms 11816 KB Output is correct
6 Correct 128 ms 11856 KB Output is correct
7 Correct 120 ms 11816 KB Output is correct
8 Correct 120 ms 11812 KB Output is correct
9 Correct 119 ms 11856 KB Output is correct
10 Correct 123 ms 11824 KB Output is correct
11 Correct 122 ms 11828 KB Output is correct
12 Correct 123 ms 11828 KB Output is correct
13 Correct 118 ms 11812 KB Output is correct
14 Correct 121 ms 11852 KB Output is correct
15 Correct 119 ms 11856 KB Output is correct
16 Correct 118 ms 11860 KB Output is correct
17 Correct 116 ms 8620 KB Output is correct

Subtask #2
0.0 / 90.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3810 ms 11812 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -