oj.uz

Submission #54364

# Submission time Handle Problem Language Result Execution time Memory
54364 2018-07-03T08:56:04 Z 윤교준(#1474) Aliens (IOI07_aliens) C++11
100 / 100
 6 ms 588 KB 
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define INF (0x3f3f3f3f)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

unordered_map<ll, bool> MP;

ll L, SX, SY;
ll N, X, Y;

bool ask(ll x, ll y) {
	if(x < 1 || y < 1 || N < x || N < y) return false;
	ll key = x * 2000000001 + y;
	auto it = MP.find(key);
	if(MP.end() != it) return it->second;

	printf("examine %lld %lld\n", x, y);
	fflush(stdout);

	char str[11];
	scanf(" %s", str);
	return (MP[key] = ('t' == str[0]));
}
void answer(ll x, ll y) {
	printf("solution %lld %lld\n", x, y);
	fflush(stdout);
}
void answerLD(ll x, ll y) {
	answer(x + L/2, y + L/2);
}

void findL() {
	{
		ll k = 1;
		for(;; k <<= 1) {
			if(ask(X-k, Y)) continue;
			break;
		}
		if(1 == k) {
			SX = X;
		} else {
			k >>= 1;
			if(!ask(X-k-1, Y)) {
				SX = X-k;
			} else {
				ll s = X-(k<<1)+1, e = X-k-1;
				for(ll m; s < e;) {
					m = (s+e)/2;
					if(ask(m, Y)) e = m;
					else s = m+1;
				}
				SX = s;
			}
		}
	}
	{
		ll k = 1;
		for(;; k <<= 1) {
			if(ask(X+k, Y)) continue;
			break;
		}
		if(1 == k) {
			L = X-SX+1;
		} else {
			k >>= 1;
			if(!ask(X+k+1, Y)) {
				L = X+k-SX+1;
			} else {
				ll s = X+k+1, e = X+(k<<1)-1;
				for(ll m; s < e;) {
					m = (s+e+1)/2;
					if(ask(m, Y)) s = m;
					else e = m-1;
				}
				L = s-SX+1;
			}
		}
	}
	{
		ll s = Y, e = Y+L-1; for(ll m; s < e;) {
			m = (s+e+1)/2;
			if(ask(SX, m)) s = m;
			else e = m-1;
		}
		SY = s-L+1;
	}

	//printf("TEST %lld %lld : %lld\n", SX, SY, L);
}

void oddprocess() {
	if(ask(SX, SY+L*4)) {
		answerLD(SX, SY+L*2);
		return;
	}
	if(ask(SX, SY-L*4)) {
		answerLD(SX, SY-L*2);
		return;
	}
	answerLD(SX, SY);
}

void evenprocess() {
	if(ask(SX+L, SY+L*3)) {
		answerLD(SX+L, SY+L);
		return;
	}
	answerLD(SX+L, SY-L);
}

void process() {
	if(ask(SX-L*4, SY)) {
		SX = SX - L*2;
		oddprocess();
		return;
	}
	if(ask(SX+L*4, SY)) {
		SX = SX + L*2;
		oddprocess();
		return;
	}
	bool l = ask(SX-L*2, SY), r = ask(SX+L*2, SY);
	if(l && r) {
		oddprocess();
		return;
	}
	if(l) {
		SX = SX-L*2;
		evenprocess();
		return;
	}
	if(r) {
		evenprocess();
		return;
	}
	puts("WTF?");
	exit(-1);
}

int main() {
	scanf("%lld%lld%lld", &N, &X, &Y);
	findL();
    process();
	return 0;
}

Compilation message

aliens.cpp: In function 'bool ask(ll, ll)':
aliens.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf(" %s", str);
  ~~~~~^~~~~~~~~~~~
aliens.cpp: In function 'int main()':
aliens.cpp:148:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld", &N, &X, &Y);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 440 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 440 KB Output is correct
2 Correct 2 ms 452 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 476 KB Output is correct
2 Correct 2 ms 516 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 520 KB Output is correct
2 Correct 2 ms 528 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 528 KB Output is correct
2 Correct 2 ms 560 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 560 KB Output is correct
2 Correct 3 ms 564 KB Output is correct
3 Correct 3 ms 572 KB Output is correct

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 580 KB Output is correct
2 Correct 3 ms 588 KB Output is correct
3 Correct 3 ms 588 KB Output is correct

Subtask #10
10.0 / 10.0

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