oj.uz

답안 #282365

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
282365 2020-08-24T11:01:38 Z Kastanda Hotter Colder (IOI10_hottercolder) C++11
90 / 100
 778 ms 24544 KB 
// M
#include<bits/stdc++.h>
#include "grader.h"
using namespace std;
int n;
int SolveType2(int l, int r)
{
        assert(l - 1 >= r - l + 1);
        assert(n - r >= r - l + 1);

        int last = l;
        Guess(l);

        while (l < r)
        {
                int tobe = -1;
                if (last <= l)
                        tobe = r + (l - last);
                else if (last >= r)
                        tobe = l - (last - r);
                else
                        assert(0);

                assert(tobe >= 1 && tobe <= n);

                int w = Guess(tobe);
                if (w == 0)
                        return (last + tobe) / 2;

                if (l + 1 == r)
                {
                        if ((w == 1 && tobe > last) || (w == -1 && tobe < last))
                                return r;
                        return l;
                }

                if ((w == 1 && tobe > last) || (w == -1 && tobe < last))
                        l = (l + r) / 2 + 1;
                else
                        r = (l + r - 1) / 2;

                last = tobe;
        }
        assert(l == r);
        return l;
}
int SolveType1(int l, int r, int asked = 0)
{
        if (r - l == 0)
                return l;

        if (!asked)
                Guess(l);

        if (r - l == 1)
        {
                int w = Guess(r);
                if (w == 1)
                        return r;
                return l;
        }
        if (r - l == 2)
        {
                int w = Guess(r);
                if (w == 1)
                        return r;
                if (w == 0)
                        return r - 1;
                return l;
        }
        int md = (r - l + 1) / 3 * 2 + l - 1;

        int w = Guess(md);
        if (w == 0)
                return (l + md) / 2;
        if (w == -1)
                return SolveType1(l, (l + md - 1) / 2);

        assert(md + 2 <= r);
        w = Guess(md + 2);
        if (w == 0)
                return md + 1;
        if (w == 1)
                return SolveType1(md + 2, r, 1);

        return SolveType2((l + md) / 2 + 1, md);
}
int HC(int _n)
{
        n = _n;
        return SolveType1(1, n);
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 1280 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 1280 KB Output is correct

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 1280 KB Output is correct

Subtask #4
15.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 778 ms 24544 KB Output is partially correct - alpha = 0.600000000000