Submission #989706

#	Time	Username	Problem	Language	Result	Execution time	Memory
989706		dnass	Aliens (IOI07_aliens)	C++17	100 / 100	2 ms	344 KiB

aliens

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10