oj.uz

Submission #402189

# Submission time Handle Problem Language Result Execution time Memory
402189 2021-05-11T12:05:49 Z IloveN Hotter Colder (IOI10_hottercolder) C++14
83 / 100
 649 ms 9024 KB 
#include<bits/stdc++.h>
#include "grader.h"

using namespace std;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(vr) vr.begin(),vr.end()
#define vi vector<int>
#define vll vector<ll>
namespace myrand
{
    mt19937 mt(chrono::system_clock::now().time_since_epoch() / chrono::microseconds(1));
    ll Int(ll l,ll r) {return uniform_int_distribution<ll> (l,r)(mt);}
}

using namespace myrand;
const int N = 1e5 + 10;

int HC(int n){
    if (n == 1) return 1;
    Guess(1);
    int g = Guess(n);
    int prv = n;
    int side, l = 1, r = n; // 0 = left, 1 = right
    if (g == 0) return (n + 1) / 2;
    if (g == 1) side = 1, l = (n + 1) / 2 + 1;
    else side = 0, r = n / 2;
    if (side == 0)
        while (r - l + 1 > 3)
        {
            Guess(1);
            int mid = r / 4 + 1;
            g = Guess(mid * 2 - 1);
            if (g == 0) return mid;
            if (g == -1) r = mid - 1;
            else
            {
                l = mid + 1;
                if (r - l + 1 <= 3) break;
                Guess(r);
                g = Guess(l);
                prv = l;
                if (g == 0) return (l + r) / 2;
                if (g == -1)
                {
                    l = (l + r) / 2 + 1;
                    break;
                }
                else r = (l + r - 1) / 2;
                g = Guess(r);
                prv = r;
                if (g == 0) return (l + r) / 2;
                if (g == 1) l = (l + r) / 2 + 1;
                else r = (l + r - 1) / 2;
                break;
            }
        }
    else
        while (r - l + 1 > 3)
        {
            Guess(n);
            int mid = n - (n - l + 1) / 4;
            g = Guess(mid * 2 - n);
            if (g == 0) return mid;
            if (g == -1) l = mid + 1;
            else
            {
                r = mid - 1;
                if (r - l + 1 <= 3) break;
                Guess(l);
                g = Guess(r);
                prv = r;
                if (g == 0) return (l + r) / 2;
                if (g == 1) l = (l + r) / 2 + 1;
                else
                {
                    r = (l + r - 1) / 2;
                    break;
                }
                g = Guess(l);
                prv = l;
                if (g == 0) return (l + r) / 2;
                if (g == -1) l = (l + r) / 2 + 1;
                else r = (l + r - 1) / 2;
                break;
            }
        }
    if (l == r) return l;
    if (r - l + 1 <= 3)
    {
        Guess(l);
        g = Guess(r);
        if (g == 0) return (l + r) / 2;
        if (g == 1) return r;
        return l;
    }
    Guess(l);
    prv = l;
    while (l < r)
    {
        int mid = (l + r) / 2;
        if (prv <= l)
        {
            g = Guess(r + l - prv);
            prv = r + l - prv;
            if (g == 0) return mid;
            if (g == -1) r = mid;
            else l = mid + 1;
        }
        else
        {
            g = Guess(l - (prv - r));
            prv = l - (prv - r);
            if (g == 0) return mid;
            if (g == -1) l = mid + 1;
            else r = mid;
        }
    }
    return l;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1228 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1228 KB Output is correct

Subtask #3
25.0 / 25.0

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

Subtask #4
8.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 649 ms 9024 KB Output is partially correct - alpha = 0.333333333333