oj.uz

Submission #91673

# Submission time Handle Problem Language Result Execution time Memory
91673 2018-12-29T06:47:20 Z Retro3014 Aliens (IOI07_aliens) C++17
0 / 100
 1000 ms 380 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
using namespace std;

int N;
struct P{
    int x, y;
};
typedef long long ll;
struct P2{
    ll x, y;
};
P2 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<SQ> v(1);
string str;
set<pair<int, int>> s;

bool examine(int x, int y){
    if(x<1 || x>N || y<1 || y>N)    return false;
    printf("examine %d %d\n", x, y);
    cin>>str;
    return (str[0]=='t');
}

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


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

Compilation message

aliens.cpp: In function 'int main()':
aliens.cpp:104:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(i<v.size()){
           ~^~~~~~~~~
aliens.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &N, &st.x, &st.y);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3045 ms 248 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3055 ms 248 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3035 ms 376 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3041 ms 376 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3034 ms 248 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3044 ms 380 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3048 ms 248 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3014 ms 248 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3035 ms 376 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3036 ms 248 KB Time limit exceeded
2 Halted 0 ms 0 KB -