oj.uz

Submission #1058860

# Submission time Handle Problem Language Result Execution time Memory
1058860 2024-08-14T14:35:41 Z rainboy COVID tests (CEOI24_covid) C
100 / 100
 1323 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 (r == 0)
		return;
	else 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:81:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |  scanf("%d%lf%d", &n, &p, &t), m = 1 / p * 4, subtask = t == 1 ? 1 : 2, init();
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.c:93:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |   scanf("%*s");
      |   ^~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct

Subtask #1
10.0 / 10.0

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

Subtask #2
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 11812 KB Output is correct (P=0.001, F=15.1, Q=10.9) -> 90.00 points
2 Correct 191 ms 11856 KB Output is correct (P=0.005256, F=51.1, Q=46.3) -> 90.00 points
3 Correct 264 ms 11812 KB Output is correct (P=0.011546, F=94.9, Q=90.6) -> 90.00 points
4 Correct 427 ms 11812 KB Output is correct (P=0.028545, F=191.5, Q=187.7) -> 90.00 points
5 Correct 482 ms 11856 KB Output is correct (P=0.039856, F=246.3, Q=243.7) -> 90.00 points
6 Correct 596 ms 11828 KB Output is correct (P=0.068648, F=366.2, Q=364.2) -> 90.00 points
7 Correct 889 ms 11856 KB Output is correct (P=0.104571, F=490.3, Q=488.1) -> 90.00 points
8 Correct 1137 ms 11808 KB Output is correct (P=0.158765, F=639.1, Q=633.2) -> 90.00 points
9 Correct 1323 ms 11856 KB Output is correct (P=0.2, F=731.4, Q=729.3) -> 90.00 points