oj.uz

Submission #222774

# Submission time Handle Problem Language Result Execution time Memory
222774 2020-04-14T01:49:06 Z mathking1021 Hotter Colder (IOI10_hottercolder) C++11
81 / 100
 702 ms 8184 KB 
#include "grader.h"
#include <iostream>

using namespace std;

int ans = 0;
int n = 0;

//void init()
//{
//    const int M = 50000000;
//    ve.push_back(1), ve.push_back(1), ve.push_back(3);
//    while(ve.back() < M)
//    {
//        ve.push_back(ve[ve.size() - 2] + ve[ve.size() - 1] + 1);
//    }
//}

void f(int p, int q, int r)
{
    if(p == q)
    {
        ans = p;
        return;
    }
    if(r == 0)
    {
        Guess((p + q - 1) / 2);
        int t = Guess(p + q - (p + q - 1) / 2);
        if(t == 1)
        {
            f((p + q + 2) / 2, q, p + q - (p + q - 1) / 2);
        }
        else if(t == -1)
        {
            f(p, (p + q - 1) / 2, p + q - (p + q - 1) / 2);
        }
        else
        {
            ans = (p + q) / 2;
        }
        return;
    }
    int t = p + q - r;
    if(t < 1 || t > n)
    {
        Guess((p + q - 1) / 2);
        int x = Guess(p + q - (p + q - 1) / 2);
        if(x == 1)
        {
            f((p + q + 2) / 2, q, p + q - (p + q - 1) / 2);
        }
        else if(x == -1)
        {
            f(p, (p + q - 1) / 2, p + q - (p + q - 1) / 2);
        }
        else
        {
            ans = (p + q) / 2;
        }
        return;
    }
    int y = t + r;
    int x = Guess(t);
    if(x == 0)
    {
        ans = y / 2;
        return;
    }
    if((x == 1) ^ (t < r))
    {
        f((y + 2) / 2, q, t);
    }
    else
    {
        f(p, (y - 1) / 2, t);
    }
}

int HC(int N)
{
    n = N;
    ans = 0;
    f(1, n, 0);
    return ans;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1408 KB Output is correct

Subtask #2
25.0 / 25.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
6.0 / 25.0

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