oj.uz

Submission #900114

# Submission time Handle Problem Language Result Execution time Memory
900114 2024-01-07T16:13:53 Z JakobZorz Aliens (IOI07_aliens) C++17
100 / 100
 1 ms 856 KB 
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<limits.h>
#include<math.h>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<iomanip>
#include<cstring>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;
//const int MOD=1e9+7;
//typedef pair<ll,ll>Point;
//typedef pair<ll,ll>Line;
//#define x first
//#define y second
 
bool arr[50][50];
 
map<pair<ll,ll>,bool>cache;
 
ll n;
bool query(ll x,ll y){
    if(x>=n||y>=n||x<0||y<0)
        return false;
    
    if(cache.count({x,y})==0){
        cout<<"examine "<<x+1<<" "<<y+1<<endl;
        string res;
        cin>>res;
        cache[{x,y}]=res=="true";
    }
    return cache[{x,y}];
}
 
/*bool query(int x,int y){
    cout<<"\n";
    for(int y1=0;y1<n;y1++){
        for(int x1=0;x1<n;x1++){
            if(x==x1&&y==y1){
                cout<<"X";
            }else{
                cout<<(arr[x1][y1]?'#':'.');
            }
        }
        cout<<"\n";
    }
    
    if(x>=n||y>=n||x<0||y<0)
        return false;
    return arr[x][y]==1;
}*/
 
void solve(){
//    50 5
//    31 38
//    38 32
    
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    ll x=31,y=37;
    /*n=50;
    for(int x=25;x<50;x++)
        for(int y=17;y<42;y++){
            if(((x)/5+(y-2)/5)%2==0)
                arr[x][y]=1;
        }
    
    for(int y=0;y<n;y++){
        for(int x=0;x<n;x++){
            cout<<(arr[x][y]?'#':'.');
        }
        cout<<"\n";
    }*/
    cin>>n>>x>>y;
    x--;y--;
    //query(x,y);
    
    {
        ll l=x,r=x+1;
        while(query(r,y)){
            r=l+(r-l)*2;
        }
        
        while(l<r-1){
            ll m=(l+r)/2;
            if(query(m,y)){
                l=m;
            }else{
                r=m;
            }
        }
        x=l;
    }
    
    {
        ll l=y,r=y+1;
        while(query(x,r)){
            r=l+(r-l)*2;
        }
        
        while(l<r-1){
            ll m=(l+r)/2;
            if(query(x,m)){
                l=m;
            }else{
                r=m;
            }
        }
        y=l;
    }
    
    ll size=0;
    {
        ll l=x-1,r=x;
        while(query(l,y)){
            l=r-(r-l)*2;
        }
        
        while(l<r-1){
            ll m=(l+r)/2;
            if(query(m,y)){
                r=m;
            }else{
                l=m;
            }
        }
        
        size=x-l;
    }
    
    while(query(x+2*size,y))
        x+=size*2;
    
    while(query(x,y+2*size))
        y+=size*2;
    
    if(query(x+size,y+size)){
        x+=size;
        y+=size;
    }
    
    ll offset=2*size+size/2;
    //query(x-offset,y-offset);
    cout<<"solution "<<x-offset+1<<" "<<y-offset+1<<"\n";
}
 
int main(){
    ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
    //freopen("bank.in","r",stdin);freopen("bank.out","w",stdout);
    int t=1;//cin>>t;
    while(t--)solve();
    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 1 ms 344 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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