oj.uz

Submission #119272

# Submission time Handle Problem Language Result Execution time Memory
119272 2019-06-20T20:16:03 Z eriksuenderhauf Aliens (IOI07_aliens) C++11
80 / 100
 1000 ms 384 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define mem(a,v) memset((a), (v), sizeof (a))
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%I64d", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%I64d\n", (n))
#define pii pair<int, int>
#define pil pair<int, long long>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vil vector<pil>
#define vll vector<pll>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 1e6 + 5;
const double eps = 1e-9;
char resp[30];
int n, x, y;

bool qry(int x0, int y0) {
	if (x0 > n || y0 > n || x0 < 1 || y0 < 1)
		return false;
	printf("examine %d %d\n", x0, y0);
	fflush(stdout);
	scanf("%s", resp);
	return resp[0] == 't';
}

int solveX(int dir) {
	for (int i = 1;; i *= 2) {
		if (qry(x + i * dir, y)) continue;
		if (i == 1) return x;
		int lo = x + dir * i / 2, hi = x + dir * i;
		while (abs(hi - lo) > 1) {
			int mi = (lo + hi) / 2;
			if (qry(mi, y))
				lo = mi;
			else
				hi = mi;
		}
		return lo;
	}
	return dir > 0 ? n : 1;
}

int solveY(int dir) {
	for (int i = 1;; i *= 2) {
		if (qry(x, y + i * dir)) continue;
		if (i == 1) return y;
		int lo = y + dir * i / 2, hi = y + dir * i;
		while (abs(hi - lo) > 1) {
			int mi = (lo + hi) / 2;
			if (qry(x, mi))
				lo = mi;
			else
				hi = mi;
		}
		return lo;
	}
	return dir > 0 ? n : 1;
}

int cnt[4];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main() {
	scanf("%d %d %d", &n, &x, &y);
	int mxx = solveX(1), mix = solveX(-1);
	int mxy = solveY(1), miy = solveY(-1);
	x = (mxx+mix) / 2;
	y = (mxy+miy) / 2;
	int m = mxx - mix + 1;
	for (int i = 0; i < 4; i++) {
		for (cnt[i] = 1; qry(x + 2 * m * dx[i] * cnt[i], y + 2 * m * dy[i] * cnt[i]); cnt[i]++);
		cnt[i]--;
	}
	if (cnt[0] == cnt[2] && cnt[1] == cnt[3])
		return !printf("solution %d %d\n", x, y);
	x = x + m * (cnt[0] * dx[0] + cnt[2] * dx[2]);
	y = y + m * (cnt[1] * dy[1] + cnt[3] * dy[3]);
	printf("solution %d %d\n", x, y);
    return 0;
}

Compilation message

aliens.cpp: In function 'bool qry(int, int)':
aliens.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", resp);
  ~~~~~^~~~~~~~~~~~
aliens.cpp: In function 'int main()':
aliens.cpp:88:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &x, &y);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Execution timed out 3005 ms 384 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Execution timed out 3016 ms 256 KB Time limit exceeded
3 Halted 0 ms 0 KB -