Submission #1188156

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188156		kl0989e	Worm Worries (BOI18_worm)	C++20	69 / 100	267 ms	6028 KiB

worm

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll,ll>
#define all(x) (x).begin(),(x).end()

map<array<int,3>,int> mem;
int n, m, k, q;

int mxx=-1,mxy=-1;

int query(int x=1, int y=1, int z=1) {
	/*if (k==1 && mem[{mxx,mxy,1}]<mem[{x,y,z}]) {
		mxx=x;
		mxy=y;
	}*/
	if (mem.count({x,y,z})) {
		return mem[{x,y,z}]; 
	}
	if (x<1 || n<x || y<1 || m<y || z<1 || k<z) {
		return 0;
	}
	printf("? %d %d %d\n", x, y, z);
	fflush(stdout);
	int ans = -1;
	(void)scanf("%d", &ans);
	if (ans == -1) exit(0);
	mem[{x,y,z}]=ans;
	if (k==1 && mem[{mxx,mxy,1}]<ans) {
		mxx=x;
		mxy=y;
	}
	return ans;
}

__attribute__((noreturn))
void guess(int x=1, int y=1, int z=1) {
	printf("! %d %d %d\n", x, y, z);
	exit(0);
}

double phi=(1+sqrt(5))/2;

int mean(int l, int r) {
	return l+(r-l+1)/phi;
}

int find(int l, int r, int x) {
	if (l==r) {
		return x;
	}
	int y=mean(l,r);
	if(2*x>l+r) {
		y=l+r-y;
	}
	if (x==y) {
		y++;
	}
	if (x>y) {
		swap(x,y);
	}
	if (query(x)<=query(y)) {
		return find(x+1,r,y);
	}
	else {
		return find(l,y-1,x);
	}
}

vi ax={1,-1,0,0,0,0};
vi ay={0,0,1,-1,0,0};
vi az={0,0,0,0,1,-1};

int main() {
	(void)scanf("%d %d %d %d", &n, &m, &k, &q);
	if (m==1 && k==1) {
		guess(find(1,n,mean(1,n)));
	}
	if (k==1) {
		/*for (int seed=108; seed<1e9; seed++) {
		mxx=-1;
		mxy=-1;
		mt19937 rnd(seed);
		for (int i=1; i<=n; i++) {
			for (int j=1; j<=n; j++) {
				mem[{i,j,1}]=rnd()%100000;
				cout << mem[{i,j,1}] << ' ';
			}
			cout << endl;
		}*/
		int lx=1,rx=n;
		int ly=1,ry=m;
		for (int i=0; lx<=rx && ly<=ry; i++) {
			if (i%2) {
				int mix=lx+(rx-lx)/2;
				int tmx=-1;
				for (int j=ly; j<=ry; j++) {
					if (query(mix,j)>query(mix,tmx)) {
						tmx=j;
					}
				}
				if (max(query(mix-1,tmx),query(mix+1,tmx))<=query(mix,tmx) && (ly!=tmx || query(mix,tmx-1)<=query(mix,tmx) && (ry!=tmx || query(mix,tmx+1)<=query(mix,tmx)))) {
					mxx=mix;
					mxy=tmx;
					break;
				}
				if (mxx>mix) {
					lx=mix+1;
				}
				else {
					rx=mix-1;
				}
			}
			else {
				int mix=ly+(ry-ly)/2;
				int tmx=-1;
				for (int j=lx; j<=rx; j++) {
					if (query(j,mix)>query(tmx,mix)) {
						tmx=j;
					}
				}
				if (max(query(tmx,mix-1),query(tmx,mix+1))<=query(tmx,mix)) {
					mxx=tmx;
					mxy=mix;
					break;
				}
				if (mxy>mix) {
					ly=mix+1;
				}
				else {
					ry=mix-1;
				}
			}
		}
		/*for (int i=0; i<4; i++) {
			if (mem[{mxx+ax[i],mxy+ay[i],1}]>query(mxx,mxy)) {
				cout << seed << " NOK\n";
				return 0;
			}
		}*/
		guess(mxx,mxy);
		/*if (seed%1000==0) {
			cout << seed << endl;
		}
		}*/
	}
	mt19937_64 rnd(time(0));
	int mx=-1,x,y,z;
	for (int i=0; i<q/2; i++) {
		int tx=rnd()%n+1;
		int ty=rnd()%m+1;
		int tz=rnd()%k+1;
		if (query(tx,ty,tz)>mx) {
			mx=query(tx,ty,tz);
			x=tx;
			y=ty;
			z=tz;
		}
	}
	while (1) {
		mx=-1;
		int nx,ny,nz;
		for (int i=0; i<6; i++) {
			if (query(x+ax[i],y+ay[i],z+az[i])>mx) {
				nx=x+ax[i];
				ny=y+ay[i];
				nz=z+az[i];
				mx=query(nx,ny,nz);
			}
		}
		if (mx<=query(x,y,z)) {
			guess(x,y,z);
		}
		x=nx;
		y=ny;
		z=nz;
	}
}

Compilation message (stderr)

worm.cpp: In function 'int query(int, int, int)':
worm.cpp:33:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         (void)scanf("%d", &ans);
      |               ~~~~~^~~~~~~~~~~~
worm.cpp: In function 'int main()':
worm.cpp:82:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |         (void)scanf("%d %d %d %d", &n, &m, &k, &q);
      |               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 22 / 22
• Subtask 3: 0 / 12
• Subtask 4: 0 / 19
• Subtask 5: 14 / 14
• Subtask 6: 23 / 23