oj.uz

Submission #282377

# Submission time Handle Problem Language Result Execution time Memory
282377 2020-08-24T11:12:26 Z Kastanda Hotter Colder (IOI10_hottercolder) C++11
90 / 100
 712 ms 8184 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 Brute(int l, int r)
{
        int last = l;
        while (l < r)
        {
                if (last != l && last != r)
                        last = r, Guess(last);

                if (last == l)
                {
                        int w = Guess(r);
                        last = r;
                        if (w == 0)
                                return (l + r) / 2;
                        else if (w == 1)
                                l = (l + r) / 2 + 1;
                        else
                                r = (l + r - 1) / 2;
                        continue;
                }
                assert(last == r);
                if (last == r)
                {
                        int w = Guess(l);
                        last = l;
                        if (w == 0)
                                return (l + r) / 2;
                        else if (w == 1)
                                r = (l + r - 1) / 2;
                        else
                                l = (l + r) / 2 + 1;
                        continue;
                }
        }
        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;
        }

        if (r - l <= 5)
                return Brute(l, r);

        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

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1280 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1280 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1280 KB Output is correct

Subtask #4
15.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 712 ms 8184 KB Output is partially correct - alpha = 0.600000000000