Submission #544738

#	Time	Username	Problem	Language	Result	Execution time	Memory
544738		rainboy	Worm Worries (BOI18_worm)	C11	100 / 100	664 ms	336 KiB

worm

/* 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 (stderr)

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 / 10
• Subtask 2: 22 / 22
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 14 / 14
• Subtask 6: 23 / 23