제출 #1339517

#제출 시각아이디문제언어결과실행 시간메모리
1339517po_rag526Aliens (IOI07_aliens)C++20
0 / 100
1 ms444 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;
// array<int,3> merge(array<int,3> a,array<int,3> b) {
//     array<int,3> res = {min(a[0],b[0]),max(a[1],b[1]),max({a[2],b[2],b[1]-a[0]})};
//     return res;
// }


// void update(int v,int l,int r,int p,pair<int,int> ele,vector<array<int,3>>& seg) {
//     if (l==r && p == r) seg[v] = {ele.second,ele.second,0};
//     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);
    auto valid = [&](int x) -> bool {
        return x >= 1 && x <= n;
    };
    int r=y0;
    int l= y0;
    int rt = x0;
    int ld = x0;
    int mx_j=0;
    rep(j,0,30) {
        int p = (1LL << j);
        if((valid(y0+p) && !query(x0,y0+p)) || !valid(y0+p)) {
            mx_j=j;
            break;
        }
    }
    rrep(j,mx_j-1,0) {
        int p = (1LL<<j);
        if(valid(r+p) && query(x0,r+p)) {
            r+=p;
        }    
    }
    mx_j=0;
    rep(j,0,30) {
        int p = (1LL << j);
        if((valid(y0-p) && !query(x0,y0-p)) || !valid(y0-p)) {
            mx_j=j;
            break;
        }
    }
    rrep(j,mx_j-1,0) {
        int p = (1LL<<j);
        if(valid(l-p) && query(x0,l-p)) {
            l-=p;
        }    
    }
    mx_j=0;
    rep(j,0,30) {
        int p = (1LL << j);
        if(valid(x0+p) && !query(x0+p,y0) || !valid(x0+p)) {
            mx_j=j;
            break;
        }
    }
    rrep(j,mx_j-1,0) {
        int p = (1LL<<j);
        if(valid(rt+p) && query(rt+p,y0)) {
            rt+=p;
        }    
    }
    mx_j=0;
    rep(j,0,30) {
        int p = (1LL << j);
        if(!valid(x0-p) || (valid(x0-p) && !query(x0-p,y0))) {
            mx_j=j;
            break;
        }
    }
    rrep(j,mx_j-1,0) {
        int p = (1LL<<j);
        if(valid(ld-p) && query(ld-p,y0)) {
            ld-=p;
        }    
    }
    cout<<ld<<" "<<rt<<endl;
    cout<<l<<" "<<r<<endl;
    x0 = (ld+rt)/2;
    y0 = (l+r)/2;
    int m = r-l+1;
    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...