oj.uz

답안 #54319

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
54319 2018-07-03T07:01:07 Z 강태규(#1471) Aliens (IOI07_aliens) C++11
90 / 100
 4 ms 596 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

llong n, sx, sy;
int query(llong x, llong y) {
    static map<pll, int> mp;
    static char s[100];
    if (x < 1 || n < x || y < 1 || n < y) return 0;
    if (x == sx && y == sy) return 1;
    if (mp.find(pll(x, y)) != mp.end()) return mp[pll(x, y)];
    if (mp.size() == 300) exit(1);
    printf("examine %lld %lld\n", x, y);
    fflush(stdout);
    scanf("%s", s);
    return mp[pll(x, y)] = (s[0] == 't');
}

int main() {
    scanf("%lld%lld%lld", &n, &sx, &sy);
    llong lt = 0, rt = 0, ut = 0, dt = 0, t = 0;
    
    {
        llong s = 1, e = sx - 1, ans = sx;
        while (s <= e) {
            llong m = (s + e) / 2;
            if (query(m, sy)) ans = m, e = m - 1;
            else s = m + 1;
        }
        lt = ans;
        if (query((ans + sx) / 2, sy)) {
            if (!query(ans + (sx - ans) / 4, sy)) {
                s = ans + (sx - ans) / 4 + 1, e = (ans + sx) / 2 - 1;
                llong ans2 = (ans + sx) / 2;
                while (s <= e) {
                    llong m = (s + e) / 2;
                    if (query(m, sy)) ans2 = m, e = m - 1;
                    else s = m + 1;
                }
                if (!t) t = ans2 - ans;
                else if (t != ans2 - ans) exit(1);
            }
        }
        else {
            s = (ans + sx) / 2 + 1, e = sx - 1;
            llong ans2 = sx;
            while (s <= e) {
                llong m = (s + e) / 2;
                if (query(m, sy)) ans2 = m, e = m - 1;
                else s = m + 1;
            }
            if (!t) t = ans2 - ans;
            else if (t != ans2 - ans) exit(1);
        }
    }
    
    {
        llong s = sx + 1, e = n, ans = sx;
        while (s <= e) {
            llong m = (s + e) / 2;
            if (query(m, sy)) ans = m, s = m + 1;
            else e = m - 1;
        }
        rt = ans;
        if (query((ans + sx) / 2, sy)) {
            if (!query(ans - (ans - sx) / 4, sy)) {
                s = (ans + sx) / 2 + 1, e = ans - (ans - sx) / 4 - 1;
                llong ans2 = (ans + sx) / 2;
                while (s <= e) {
                    llong m = (s + e) / 2;
                    if (query(m, sy)) ans2 = m, s = m + 1;
                    else e = m - 1;
                }
                if (!t) t = ans - ans2;
                else if (t != ans - ans2) exit(1);
            }
        }
        else {
            s = sx + 1, e = (ans + sx) / 2 - 1;
            llong ans2 = sx;
            while (s <= e) {
                llong m = (s + e) / 2;
                if (query(m, sy)) ans2 = m, s = m + 1;
                else e = m - 1;
            }
            if (!t) t = ans - ans2;
            else if (t != ans - ans2) exit(1);
        }
    }
    
    {
        llong s = 1, e = sy - 1, ans = sy;
        while (s <= e) {
            llong m = (s + e) / 2;
            if (query(sx, m)) ans = m, e = m - 1;
            else s = m + 1;
        }
        ut = ans;
        if (query(sx, (ans + sy) / 2)) {
            if (!query(sx, ans + (sy - ans) / 4)) {
                s = ans + (sy - ans) / 4 + 1, e = (ans + sy) / 2 - 1;
                llong ans2 = (ans + sy) / 2;
                while (s <= e) {
                    llong m = (s + e) / 2;
                    if (query(sx, m)) ans2 = m, e = m - 1;
                    else s = m + 1;
                }
                if (!t) t = ans2 - ans;
                else if (t != ans2 - ans) exit(1);
            }
        }
        else {
            s = (ans + sy) / 2 + 1, e = sy - 1;
            llong ans2 = sy;
            while (s <= e) {
                llong m = (s + e) / 2;
                if (query(sx, m)) ans2 = m, e = m - 1;
                else s = m + 1;
            }
            if (!t) t = ans2 - ans;
            else if (t != ans2 - ans) exit(1);
        }
    }
    
    {
        llong s = sy + 1, e = n, ans = sy;
        while (s <= e) {
            llong m = (s + e) / 2;
            if (query(sx, m)) ans = m, s = m + 1;
            else e = m - 1;
        }
        dt = ans;
        if (query(sx, (ans + sy) / 2)) {
            if (!query(sx, ans - (ans - sy) / 4)) {
                s = (ans + sy) / 2 + 1, e = ans - (ans - sy) / 4 - 1;
                llong ans2 = (ans + sy) / 2;
                while (s <= e) {
                    llong m = (s + e) / 2;
                    if (query(sx, m)) ans2 = m, s = m + 1;
                    else e = m - 1;
                }
                if (!t) t = ans - ans2;
                else if (t != ans - ans2) exit(1);
            }
        }
        else {
            s = sy + 1, e = (ans + sy) / 2 - 1;
            llong ans2 = sy;
            while (s <= e) {
                llong m = (s + e) / 2;
                if (query(sx, m)) ans2 = m, s = m + 1;
                else e = m - 1;
            }
            if (!t) t = ans - ans2;
            else if (t != ans - ans2) exit(1);
        }
    }
    
    if (!t) t = rt - lt + 1;
    while (query(lt - t, sy)) lt -= t;
    while (query(rt + t, sy)) rt += t;
    while (query(sx, ut - t)) ut -= t;
    while (query(sx, dt + t)) dt += t;
    printf("solution %lld %lld\n", (lt + rt) / 2, (ut + dt) / 2);
    
	return 0;
}

Compilation message

aliens.cpp: In function 'int query(llong, llong)':
aliens.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", s);
     ~~~~~^~~~~~~~~
aliens.cpp: In function 'int main()':
aliens.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld%lld", &n, &sx, &sy);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 308 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 460 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 3 ms 564 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 564 KB Output is correct
2 Correct 3 ms 580 KB Output is correct

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 580 KB Output is correct
2 Incorrect 4 ms 596 KB Incorrect

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 4 ms 596 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 2 ms 596 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 3 ms 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 3 ms 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 3 ms 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct