oj.uz

답안 #887133

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
887133 2023-12-13T20:58:15 Z MilosMilutinovic Worm Worries (BOI18_worm) C++14
32 / 100
 15 ms 1020 KB 
/* https://boi2018.progolymp.se/spoiler-day1.pdf */
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}()); 
const ll mod=998244353;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

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

int ask(int x,int y,int z) {
	if (x<1||x>n||y<1||y>m||z<1||z>k) return 0;
	if (!val.count({x,y,z})) {
		printf("? %d %d %d\n",x,y,z);
		fflush(stdout);
		scanf("%d",&val[{x,y,z}]);
	}
	return val[{x,y,z}];
}

bool good(int x,int y,int z){
	if(x<1||x>n||y<1||y>m||z<1||z>k) return false;
	if (ask(x,y,z)<ask(x+1,y,z)) return false;
	if (ask(x,y,z)<ask(x,y+1,z)) return false;
	if (ask(x,y,z)<ask(x,y,z+1)) return false;
	if (ask(x,y,z)<ask(x-1,y,z)) return false;
	if (ask(x,y,z)<ask(x,y-1,z)) return false;
	if (ask(x,y,z)<ask(x,y,z-1)) return false;
	return true;
}

int main() {
	scanf("%d%d%d%d",&n,&m,&k,&q);
	if (m==1&&k==1) {
		int l=1,r=n,x=0.618*l+0.382*r,y=0.382*l+0.618*r;
		while (l+10<r) {
			if (x>=y) {
				x=0.618*l+0.382*r;
				y=0.382*l+0.618*r;
				if(x>=y) break;
			}
			if (ask(x,1,1)<ask(y,1,1)) {
				l=x+1; x=y; y=0.382*l+0.618*r;
			} else {
				r=y-1; y=x; x=0.618*l+0.382*r;
			}
		}
		int ans=l;
		rep(i,l,r+1) if (good(i,1,1)) ans=i;
		printf("! %d 1 1",ans);
		fflush(stdout);
		return 0;
	}
	if (k==1) {
		int lx=1,rx=n,ly=1,ry=m,f=0,val=0;
		PII p=mp(-1,-1);
		while (lx<rx||ly<ry) {
			if (f==0) {
				if (lx==rx) { 
					f=1; continue;
				}
				int mid=(lx+rx)/2;
				int pos=ly;
				rep(i,ly,ry+1) {
					if (ask(mid,pos,1)<ask(mid,i,1)) {
						pos=i;
					}
				}
				if (good(mid,pos,1)) {
					printf("! %d %d 1",mid,pos);
					fflush(stdout);
					return 0;
				}
				if (ask(mid,pos,1)<val) {
					if (p.fi<mid) rx=mid-1;
					else lx=mid+1;
				} else {
					p=mp(mid,pos);
					val=ask(mid,pos,1);
					int l=ask(mid-1,pos,1);
					int r=ask(mid+1,pos,1);
					if (l>r) rx=mid-1; else lx=mid+1;
				}
			} else {
				if (ly==ry) {
					f=0; continue;
				}
				int mid=(ly+ry)/2;
				int pos=lx;
				rep(i,lx,rx+1) {
					if (ask(pos,mid,1)<ask(i,mid,1)) {
						pos=i;
					}
				}
				if (good(pos,mid,1)) {
					printf("! %d %d 1",pos,mid);
					fflush(stdout);
					return 0;
				}
				if (ask(pos,mid,1)<val) {
					if (p.se<mid) ry=mid-1;
					else ly=mid+1;
				} else {	
					p=mp(pos,mid);
					val=ask(mid,pos,1);
					int l=ask(pos,mid-1,1);
					int r=ask(pos,mid+1,1);
					if (l>r) ry=mid-1; else ly=mid+1;
				}
			}
			f^=1;
		}
		printf("! %d %d 1",lx,ly);
		fflush(stdout);
		return 0;
	}
}

Compilation message

worm.cpp: In function 'int ask(int, int, int)':
worm.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |   scanf("%d",&val[{x,y,z}]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~
worm.cpp: In function 'int main()':
worm.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |  scanf("%d%d%d%d",&n,&m,&k,&q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 440 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 440 KB Output is correct
5 Correct 0 ms 344 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 448 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 440 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 436 KB Output is correct
6 Correct 0 ms 440 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 436 KB Output is correct
11 Correct 0 ms 344 KB Output is correct

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 440 KB Output is correct
2 Correct 3 ms 436 KB Output is correct
3 Correct 1 ms 440 KB Output is correct
4 Incorrect 3 ms 600 KB not a local maximum
5 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 972 KB Output is correct
2 Correct 15 ms 776 KB Output is correct
3 Correct 5 ms 692 KB Output is correct
4 Incorrect 14 ms 1020 KB not a local maximum
5 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 344 KB invalid format (must have DIMS+1 tokens). input:
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB invalid format (must have DIMS+1 tokens). input:
2 Halted 0 ms 0 KB -