oj.uz

Submission #544738

# Submission time Handle Problem Language Result Execution time Memory
544738 2022-04-02T16:16:22 Z rainboy Worm Worries (BOI18_worm) C
100 / 100
 664 ms 336 KB 
/* upsolved after reading analysis */
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
 
int n, m, l;
 
int query(int i, int j, int k) {
	int x;
 
	printf("? %d %d %d\n", i, j, k), fflush(stdout);
	scanf("%d", &x);
	if (x == -1)
		exit(0);
	return x;
}
 
void answer(int i, int j, int k) {
	printf("! %d %d %d\n", i, j, k), fflush(stdout);
	exit(0);
}
 
void solve2(int i1, int j1, int i2, int j2, int i3, int j3, int a3, int flip) {
	int i, j, j_, a_;
 
	i = (i1 + i2) / 2;
	j_ = a_ = -1;
	for (j = j1; j <= j2; j++) {
		int a = !flip ? query(i, j, 1) : query(j, i, 1);
 
		if (a_ < a)
			a_ = a, j_ = j;
	}
	if (a_ < a3) {
		if (i3 < i)
			solve2(j1, i1, j2, i - 1, j3, i3, a3, flip ^ 1);
		else
			solve2(j1, i + 1, j2, i2, j3, i3, a3, flip ^ 1);
	} else if (i > i1 && a_ < (!flip ? query(i - 1, j_, 1) : query(j_, i - 1, 1)))
		solve2(j1, i1, j2, i - 1, j_, i, a_, flip ^ 1);
	else if (i < i2 && a_ < (!flip ? query(i + 1, j_, 1) : query(j_, i + 1, 1)))
		solve2(j1, i + 1, j2, i2, j_, i, a_, flip ^ 1);
	else if (!flip)
		answer(i, j_, 1);
	else
		answer(j_, i, 1);
}
 
int main() {
	int q;
 
	srand(12345);
	scanf("%d%d%d%d", &n, &m, &l, &q);
	if (m == 1 && l == 1) {
		double phi = (1 + sqrt(5)) / 2;
		int lower, upper, mid, a;
 
		lower = 0, upper = n + 1, mid = lower + (int) (upper - lower - 1) / phi + 1, a = query(mid, 1, 1);
		while (upper - lower > 2)
			if (mid - lower > upper - mid) {
				int mid_ = lower + (int) ((mid - lower - 1) / phi) + 1, a_ = query(mid_, 1, 1);
 
				if (a < a_)
					upper = mid, mid = mid_, a = a_;
				else
					lower = mid_;
			} else {
				int mid_ = upper - (int) ((upper - mid - 1) / phi) - 1, a_ = query(mid_, 1, 1);
 
				if (a < a_)
					lower = mid, mid = mid_, a = a_;
				else
					upper = mid_;
			}
		answer(mid, 1, 1);
	} else if (l == 1)
		solve2(1, 1, n, m, -1, -1, -1, 0);
	else {
		int h, i, j, k, a, i_, j_, k_, a_;
 
		i_ = j_ = k_ = a_ = -1;
		for (h = 0; h < q / 2; h++) {
			i = rand() % n + 1, j = rand() % m + 1, k = rand() % l + 1, a = query(i, j, k);
			if (a_ < a)
				a_ = a, i_ = i, j_ = j, k_ = k;
		}
		i = i_, j = j_, k = k_, a = a_;
		while (1)
			if (i > 1 && a < (a_ = query(i - 1, j, k)))
				a = a_, i--;
			else if (i < n && a < (a_ = query(i + 1, j, k)))
				a = a_, i++;
			else if (j > 1 && a < (a_ = query(i, j - 1, k)))
				a = a_, j--;
			else if (j < m && a < (a_ = query(i, j + 1, k)))
				a = a_, j++;
			else if (k > 1 && a < (a_ = query(i, j, k - 1)))
				a = a_, k--;
			else if (k < l && a < (a_ = query(i, j, k + 1)))
				a = a_, k++;
			else
				break;
		answer(i, j, k);
	}
	return 0;
}

Compilation message

worm.c: In function 'query':
worm.c:12:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |  scanf("%d", &x);
      |  ^~~~~~~~~~~~~~~
worm.c: In function 'main':
worm.c:53:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |  scanf("%d%d%d%d", &n, &m, &l, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 0 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 1 ms 208 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 1 ms 208 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Output is correct
2 Correct 3 ms 208 KB Output is correct
3 Correct 2 ms 208 KB Output is correct
4 Correct 4 ms 208 KB Output is correct
5 Correct 5 ms 208 KB Output is correct
6 Correct 3 ms 208 KB Output is correct
7 Correct 4 ms 208 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 208 KB Output is correct
2 Correct 24 ms 208 KB Output is correct
3 Correct 8 ms 208 KB Output is correct
4 Correct 25 ms 208 KB Output is correct
5 Correct 23 ms 208 KB Output is correct
6 Correct 24 ms 208 KB Output is correct
7 Correct 23 ms 208 KB Output is correct
8 Correct 19 ms 208 KB Output is correct
9 Correct 23 ms 208 KB Output is correct
10 Correct 14 ms 208 KB Output is correct
11 Correct 25 ms 208 KB Output is correct
12 Correct 25 ms 208 KB Output is correct
13 Correct 24 ms 208 KB Output is correct
14 Correct 27 ms 208 KB Output is correct
15 Correct 25 ms 208 KB Output is correct
16 Correct 12 ms 208 KB Output is correct
17 Correct 24 ms 208 KB Output is correct
18 Correct 22 ms 208 KB Output is correct
19 Correct 18 ms 208 KB Output is correct
20 Correct 16 ms 208 KB Output is correct
21 Correct 24 ms 208 KB Output is correct
22 Correct 21 ms 208 KB Output is correct
23 Correct 23 ms 208 KB Output is correct
24 Correct 21 ms 208 KB Output is correct
25 Correct 11 ms 208 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 357 ms 208 KB Output is correct
2 Correct 265 ms 208 KB Output is correct
3 Correct 394 ms 208 KB Output is correct
4 Correct 382 ms 208 KB Output is correct
5 Correct 341 ms 208 KB Output is correct
6 Correct 334 ms 336 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 516 ms 208 KB Output is correct
2 Correct 541 ms 208 KB Output is correct
3 Correct 493 ms 208 KB Output is correct
4 Correct 653 ms 208 KB Output is correct
5 Correct 622 ms 208 KB Output is correct
6 Correct 512 ms 208 KB Output is correct
7 Correct 521 ms 208 KB Output is correct
8 Correct 512 ms 208 KB Output is correct
9 Correct 524 ms 252 KB Output is correct
10 Correct 664 ms 248 KB Output is correct
11 Correct 587 ms 252 KB Output is correct