oj.uz

Submission #989706

# Submission time Handle Problem Language Result Execution time Memory
989706 2024-05-28T15:47:51 Z dnass Aliens (IOI07_aliens) C++17
100 / 100
 2 ms 344 KB 
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<cmath>
#include<random>
#include<bitset>
#include<string>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<deque>
#include<chrono>
using namespace std;
typedef long long int lld;
typedef long double lf;
#define INF 1000000000000000000LL
#define MOD 1000000007LL
#define ff first
#define ss second

lld n, x, y, l, r, mid, xl, xr, xmid, diff;

lld ask(lld xt, lld yt){
    if(xt<=0||yt<=0||xt>n||yt>n) return 0;
    cout << "examine " << xt << " " << yt << endl;
    string rt; cin >> rt;
    return rt[0]=='t';
}

int main(){
	cin >> n >> x >> y;
    l = x, r = n+1;
    while(l+1<r){
        lld mid = (l+r)/2;
        if(ask(mid, y)) l = mid;
        else r = mid;
    }
    x = l;
    //cout << "Found right edge: " << x << " " << y << endl;
    l = y, r = n+1;
    while(l+1<r){
        lld mid = (l+r)/2;
        if(ask(x, mid)) l = mid;
        else r = mid;
    }
    y = l;
    //cout << "Found top right of square: " << x << " " << y << endl;
    xl = x, xr = n+1, diff = y-x;
    while(xl+1<xr){
        xmid = (xl+xr)/2;
        if(ask(xmid, xmid+diff)) xl = xmid;
        else xr = xmid;
    }
    x = xl, y = xl+diff;
    //cout << "Found top right of diagonal: " << x << " " << y << endl;
    xl = 0, xr = x, diff = y-x;
    while(xl+1<xr){
        xmid = (xl+xr)/2;
        if(ask(xmid, xmid+diff)) xr = xmid;
        else xl = xmid;
    }
    x = (x+xr)/2, y = (y+xr+diff)/2;
    //cout << "Found center of diagonal: " << x << " " << y << endl;
    xl = 0, xr = x, diff = y+x;
    while(xl+1<xr){
        xmid = (xl+xr)/2;
        if(ask(xmid, diff-xmid)) xr = xmid;
        else xl = xmid;
    }
    x = xr, y = diff-xr;
    //cout << "Found top left of main diagonal: " << x << " " << y << endl;
    xl = x, xr = n+1, diff = y+x;
    while(xl+1<xr){
        xmid = (xl+xr)/2;
        if(ask(xmid, diff-xmid)) xl = xmid;
        else xr = xmid;
    }
    x = (x+xl)/2, y = (y+diff-xl)/2;
    cout << "solution " << x << " " << y << endl;
	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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