제출 #1339098

#제출 시각아이디문제언어결과실행 시간메모리
1339098po_rag526Aliens (IOI07_aliens)C++20
0 / 100
1 ms344 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
#define int long long
#define ll long long
#define mkp(a,b) make_pair(a,b)
#define rep(i,a,b) for (int i = a; i < b; i++)
#define rrep(i,a,b) for (int i = a; i >= b; i--)
#define endl '\n'
#define pb push_back
 
pair<int,int> mods = {1000000007,998244353};
int MD = mods.first;
ll MX_ll = 1e18;
int MX_VL = 2e9;
int GN = 1e5+10;
 
void N() {cout<<"NO\n";}
void Y() {cout<<"YES\n";}
void isTrue(const bool ope) {if (ope) Y();else N();}
int pw(int x,int t) {int res = 1;while (t--) res *= x;return res;}
int lg(int x,int b) {int res = 0;while (x >= b) {x/=b;res++;}return res;}
int sqr_t(int x) {
    if (x==0)return 0;int l = 1;int r = x;int res = 1;while (l<=r) {int m = (l+r)/2;if (m*m == x)return m;if (m*m>x) {r = m-1;} else {res = m;l = m+1;}}
    return res;
}
int fastPow(int x,int p) {
    int res = 1;
    while (p) {
        if (p%2) {
            res = (x*res)%MD;
        }
        x = (x*x)%MD;
        p = (p>>1);
    }
    return res;
}
int pwdiv(int x,int y) {
    int res = (x*fastPow(y,MD-2))%MD;
    return res;
}
 
int mdb(int x,int md) {
    int res = x%md;
    return res < 0 ? res+md : res;
}
 
int neutral = MX_ll;
pair<int,int> merge1(pair<int,int> a,pair<int,int> b) {
    int c1 = b.second-a.first;
    int c2 = b.second-b.first;
    int c3 = a.second-a.first;
    int mx = max({c1,c2,c3});
    if(mx==c1) {
        return mkp(a.first,b.second);
    } 
    if(mx==c2) {
        return b;
    }
    return a;
}
pair<int,int> merge2(pair<int,int> a,pair<int,int> b) {
    int c1 = a.second-b.first;
    int c2 = b.second-b.first;
    int c3 = a.second-a.first;
    int mx = max({c1,c2,c3});
    if(mx==c1) {
        return mkp(b.first,a.second);
    } 
    if(mx==c2) {
        return b;
    }
    return a;
}

void update(int v,int l,int r,int p,pair<int,int> ele,vector<pair<int,int>>& seg) {
    if (l==r && p == r) seg[v] = mkp(ele.second,ele.second);
    else if (l <= p && r >= p) {
        int m = (l+r)/2;
        update(2*v,l,m,p,ele,seg);
        update(2*v+1,m+1,r,p,ele,seg);
        if(ele.first==1) {
            seg[v] = merge1(seg[2*v],seg[2*v+1]);
        }
        else {
            seg[v] = merge2(seg[2*v],seg[2*v+1]);
            ele.first=2;
        }
    }
}
// int query(int v,int l,int r,int L,int R,vector<int>& seg) {
//     if (l >= L && r <= R) return seg[v];
//     if (r < L || l > R) return neutral;
//     int m = (l+r)/2;
//     return merge(query(2*v,l,m,L,R,seg),query(2*v+1,m+1,r,L,R,seg));
// }
 
//***-------------------------------------------------------------------------------------****


bool query(int x,int y) {
    cout<<"examine "<<y<<" "<<x<<endl;
    cout.flush();
    string s;
    cin>>s;
    if(s=="false") return false;
    return true;
}

void solve() {
    int n,x0,y0;
    cin>>n>>x0>>y0;
    swap(x0,y0);
    int L = 3;
    int R = n/5;
    int m = -1;
    auto valid = [&](int x) -> bool {
        return x>=1 && x<=n;
    };
    while (L<=R)
    {
        int md = (L+R)/2;
        int l = y0+1;
        int r = y0+m;
        int xr=-1,xl=-1,xt=-1,xb=-1;
        while (l<=r)
        {
            int p = (l+r)/2;
            if(valid(p) && !query(x0,p)) {
                xr = p-1;
                r = p-1;
            } else l = p+1;
        }
        l = y0-m;
        r=  y0-1;
        while (l<=r)
        {
            int p = (l+r)/2;
            if(valid(p) && !query(x0,p)) {
                xl = p+1;
                l = p+1;
            } else r = p-1;
        }
        l = x0+m;
        r=  x0+1;
        while (l<=r)
        {
            int p = (l+r)/2;
            if(valid(p) && !query(p,y0)) {
                xt = p-1;
                r = p-1;
            } else l = p+1;
        }
        l = x0-m;
        r=  x0-1;
        while (l<=r)
        {
            int p = (l+r)/2;
            if(valid(p) && !query(p,y0)) {
                xb = p+1;
                l = p+1;
            } else r = p-1;
        }
        if(xl==-1 && valid(y0-m)) {
            L = md+1;
            break;
        }
        if(xr==-1 && valid(y0+m)) {
            L = md+1;
            break;
        }
        if(xt==-1 && valid(x0+m)) {
            L = md+1;
            break;
        }
        if(xb==-1 && valid(x0-m)) {
            L = md+1;
            break;
        }
        if(xl==-1) xl = 1;
        if(xr==-1) xr = n;
        if(xb==-1) xb = 1;
        if(xt==-1)xt = n;
        if(xr-xl+1==md && xt-xb+1==md) {
            m = md;
            x0 = (xt+xb)/2;
            y0 = (xl+xr)/2;
            break;
        }
    }    
   
    int fr = 0;
    int bh = 0;
    int tp = 0;
    int bt = 0;
    rep(t,1,5) {
        if(y0+t*m <= n && query(x0,y0+t*m)) {
            fr++;
        }
        if(y0-t*m >= 1 && query(x0,y0-t*m)) {
            bh++;
        }
        if(x0+t*m <= n && query(x0+t*m,y0)){
            tp++;
        }
        if(x0-t*m >= 1 && query(x0-t*m,y0)){
            bt++;
        }
    }
    
    if(bh+fr==1) {
        if(fr) y0+=m;
        else y0-=m;
        if(tp) x0+=m;
        else x0 -= m;
    } else {
        if(fr==2) y0 += 2*m;
        else if(fr==0) y0 -= 2*m;
        if(tp==2) x0 += 2*m;
        else if(tp==0) x0 -= 2*m;
    }
    cout<<"solution "<<y0<<" "<<x0<<endl;
    cout.flush();
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    // cin>>t;
    while (t--) {
        solve();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...