답안 #91711

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
91711 2018-12-29T12:17:14 Z Retro3014 Aliens (IOI07_aliens) C++17
100 / 100
4 ms 504 KB
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
int N;
struct P{
    ll x, y;
};
P ans;
P st;
struct SQ{
    P lu, rd;
    P mid;
    void cmid(){
        mid.x=(lu.x+rd.x)/2;
        mid.y=(lu.y+rd.y)/2;
    }
};
vector<P> v(1);
string str;
set<pair<ll, ll>> s;
map<pair<ll, ll>, bool> mp;
char c[100];

bool chk(ll x, ll y){
    if(x<1 || x>N || y<1 || y>N)    return true;
    return false;
}

bool examine(ll x, ll y){
    if(chk(x, y))   return false;
    if(mp.find(make_pair(x, y))==mp.end()){
        printf("examine %lld %lld\n", x, y);
        fflush(stdout);
        scanf("%s", c);
        mp[make_pair(x, y)] = (c[0]=='t');
    }
    return mp[make_pair(x, y)];
}

bool examin(P a){
    return examine(a.x, a.y);
}

SQ now;
int main(){
    scanf("%d%lld%lld", &N, &st.x, &st.y);
    ll t=1, ss, ee, mi;
    P a=st;
    if(!examine(a.x, a.y+1)){
        now.lu.y = a.y;
    }else{
        while(examine(a.x, a.y+t*2))    t*=2;
        ss = a.y+t;  ee = a.y+t*2-1;
        while(ss<ee){
            if(ss==ee-1){
                if(examine(a.x, ee)) ss=ee;
                else    ee=ss;
                break;
            }
            mi=(ss+ee)/2;
            if(examine(a.x, mi))    ss = mi;
            else    ee = mi-1;
        }
        now.lu.y = ss;
    }
    a = st; t = 1;
    if(!examine(a.x, a.y-1)){
        now.rd.y = a.y;
    }else{
        while(examine(a.x, a.y-t*2))    t*=2;
        ss = a.y-t;  ee = a.y-t*2+1;
        while(ss>ee){
            mi=(ss+ee)/2;
            if(examine(a.x, mi))    ss = mi;
            else    ee = mi+1;
        }
        now.rd.y = ss;
    }
    a = st; t = 1;
    if(!examine(a.x+1, a.y)){
        now.rd.x = a.x;
    }else{
        while(examine(a.x+t*2, a.y))    t*=2;
        ss = a.x+t;  ee = a.x+t*2-1;
        while(ss<ee){
            if(ss==ee-1){
                if(examine(ee, a.y)) ss=ee;
                else    ee=ss;
                break;
            }
            mi=(ss+ee)/2;
            if(examine(mi, a.y))    ss = mi;
            else    ee = mi-1;
        }
        now.rd.x = ss;
    }
    a = st; t = 1;
    if(!examine(a.x-1, a.y)){
        now.lu.x = a.x;
    }else{
        while(examine(a.x-t*2, a.y))    t*=2;
        ss = a.x-t;  ee = a.x-t*2+1;
        while(ss>ee){
            mi=(ss+ee)/2;
            if(examine(mi, a.y))    ss = mi;
            else    ee = mi+1;
        }
        now.lu.x = ss;
    }/*
    while(1){
        if(examine(a.x, a.y+t*2)){
            t*=2;
        }else{
            if(t==1){
                if(examine(a.x, a.y+t))  a.y++;
                break;
            }else{
                a.y+=t;
                t=1;
            }
        }
    }
    now.lu.y = a.y;
    a=st;   t=1;
    while(1){
        if(examine(a.x, a.y-t*2)){
            t*=2;
        }else{
            if(t==1){
                if(examine(a.x, a.y-t)) a.y--;
                break;
            }else{
                a.y-=t; t=1;
            }
        }
    }
    now.rd.y = a.y;
    a=st; t=1;
    while(1){
        if(examine(a.x+t*2, a.y)){
            t*=2;
        }else{
            if(t==1){
                if(examine(a.x+t, a.y)) a.x++;
                break;
            }else{
                a.x+=t; t=1;
            }
        }
    }
    now.rd.x = a.x;
    a=st; t=1;
    while(1){
        if(examine(a.x-t*2, a.y)){
            t*=2;
        }else{
            if(t==1){
                if(examine(a.x-1, a.y)) a.x--;
                break;
            }else{
                a.x-=t;
                t=1;
            }
        }
    }
    now.lu.x = a.x;
    */
    now.cmid();
    v[0]=now.mid;
    int i=0;
    ll M=now.rd.x-now.lu.x+1;
    ll dx[4]={M, M, -M, -M}, dy[4]={M, -M, M, -M};
    s.insert(make_pair(v[0].x, v[0].y));
    while(i<v.size()){
        ans.x+=v[i].x;  ans.y+=v[i].y;
        for(int j=0; j<4; j++){
            if(!chk(v[i].x+dx[j], v[i].y+dy[j]) && s.find(make_pair(v[i].x+dx[j], v[i].y+dy[j]))==s.end() && examine(v[i].x+dx[j], v[i].y+dy[j])){
                s.insert(make_pair(v[i].x+dx[j], v[i].y+dy[j]));
                v.push_back({v[i].x+dx[j], v[i].y+dy[j]});
            }
        }
        i++;
    }
    printf("solution %lld %lld", ans.x/13, ans.y/13);
    fflush(stdout);
}

Compilation message

aliens.cpp: In function 'int main()':
aliens.cpp:179:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(i<v.size()){
           ~^~~~~~~~~
aliens.cpp: In function 'bool examine(ll, ll)':
aliens.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", c);
         ~~~~~^~~~~~~~~
aliens.cpp: In function 'int main()':
aliens.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%lld%lld", &N, &st.x, &st.y);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 248 KB Output is correct
3 Correct 3 ms 248 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 316 KB Output is correct
2 Correct 3 ms 248 KB Output is correct
3 Correct 4 ms 376 KB Output is correct