oj.uz

답안 #781178

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
781178 2023-07-12T21:00:00 Z raysh07 Aliens (IOI07_aliens) C++17
100 / 100
 3 ms 336 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

int n, x, y, m;
int q = 0;

map <pair<int, int>, int> memo;

bool query(int x1, int y1){
	if (x1 < 1 || x1 > n || y1 < 1 || y1 > n) return false;
	if (memo.find({x1, y1}) != memo.end()) return memo[{x1, y1}];
    cout << "examine " << x1 << " " << y1 << endl;
    q++;
    assert(q <= 300);
    string ok; cin >> ok;

    if (ok == "true") return memo[{x1, y1}] = true;
    return memo[{x1, y1}] = false;
}

bool check(int x1, int y1){
    if (!query(x1, y1)) return false;

    x1 = (x1 + x) / 2;
    y1 = (y1 + y) / 2;

    if (!query(x1, y1)) return false;

    x1 = (x1 + x) / 2;
    y1 = (y1 + y) / 2;

    if (!query(x1, y1)) return false;

    return true;
}

bool areyouok(int dx, int dy){
	int x1 = x + dx * m;
	int y1 = y + dy * m;

	return query(x1, y1);
}

void print(int l, int r, int u, int d){
	//cout << l << " " << r << " " << u << " " << d << endl;
	cout << "solution " << (l + r) / 2 << " " << (u + d) / 2 << endl;
}

void Solve()
{
    cin >> n;
    cin >> x >> y;

    int ll = 1, rl = x;
    while (ll != rl){
        int mid = (ll + rl) / 2;

        if (check(mid, y)) rl = mid;
        else ll = mid + 1;
    }

    int l = ll;

  //  cout << "FOUND OUT LEFT " << l << endl;

    ll = x, rl = n;
    while (ll != rl){
        int mid = (ll + rl + 1) / 2;

        if (check(mid, y)) ll = mid;
        else rl = mid - 1;
    }

    int r = ll;

 //   cout << "FOUND OUT RIGHT " << r << endl;

    ll = 1, rl = y;
    while (ll != rl){
        int mid = (ll + rl) / 2;

        if (check(x, mid)) rl = mid;
        else ll = mid + 1;
    }

    int u = ll;

 //   cout << "FOUND OUT UP " << u << endl;

    ll = y, rl = n;
    while (ll != rl){
        int mid = (ll + rl + 1) / 2;

        if (check(x, mid)) ll = mid;
        else rl = mid - 1;
    }

    int d = ll;

   // cout << "FOUND OUT DOWN " << d << endl;

    m = (d - u + 1);
    assert(m == (r - l + 1));

    for (int i = 0; i < 5; i++){
    	for (int j = 0; j < 5; j++){
    		if ((i + j)  % 2 == 1) continue;
    		bool good = true;

    		for (int i1 = 0; i1 < 5; i1++){
    			for (int j1 = 0; j1 < 5; j1++){
    				if ((i1 + j1) % 2 == 0){
    					good &= areyouok(i1 - i, j1 - j);
    				}
    			}
    		}

    		if (good){
    			l += m * (2 - i);
    			r += m * (2 - i);
    			u += m * (2 - j);
    			d += m * (2 - j);
    			print(l, r, u, d);
    			return;
    		}
    	}
    }
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;

   // freopen("in",  "r", stdin);
   // freopen("out", "w", stdout);

  //  cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

Compilation message

aliens.cpp: In function 'bool query(long long int, long long int)':
aliens.cpp:23:45: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   23 |     if (ok == "true") return memo[{x1, y1}] = true;
aliens.cpp:24:27: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   24 |     return memo[{x1, y1}] = false;

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 2 ms 208 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 2 ms 208 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 208 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 3 ms 336 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 2 ms 208 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 2 ms 208 KB Output is correct
3 Correct 3 ms 208 KB Output is correct