Submission #574110

#	Time	Username	Problem	Language	Result	Execution time	Memory
574110		MadokaMagicaFan	Hotter Colder (IOI10_hottercolder)	C++14	80 / 100	575 ms	8100 KiB

hottercolder

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
const ll inf = 1e9;
const int md1 = 1e9+7;
const int md2 = 998244353;

#define all(v)                      v.begin(), v.end()
#define rall(v)                     v.rbegin(), v.rend()
#define sz(v)                       ((int)v.size())

#define forn(i,n)                   for(int i = 0; i < n; ++i)
#define forbe(i,b,e)                for(int i = b; i < e; ++i)

#define pb                          push_back

#define pry                         puts("YES")
#define prn                         puts("NO")
#define endl                        '\n'

#define fst                         first
#define scn                         second

#define query(x)                    if(last != x) { val=ask(x); if(val==0&&last!=-1) return (x+last)>>1; last=x; }

int Guess(int x);

int n;
int LAST;
int R;
int cnt;

#ifdef ONPC
int
Guess(int x)
{
    ++cnt;
    #ifdef ONPC
    #ifndef ONTST
    cout << "Question: " << x << endl;
    #endif
    #endif
    if (LAST == -1) {
        LAST = x;
        return 0;
    }
    if (abs(LAST-R) > abs(x-R)) {
        LAST = x;
        return 1;
    }
    if (abs(LAST-R) < abs(x-R)) {
        LAST = x;
        return -1;
    }
    LAST = x;
    return 0;
}
#endif

int
ask(int x)
{
    assert(x>0);
    assert(x<=n);
    return Guess(x);
}

int
specialcase(int last, int l, int r)
{
    #ifdef ONPC
    #ifndef ONTST
        cout << "Special Case " << l << ' ' << r << endl;
    #endif
    #endif
    int val = 0;
    if (r == l) return l;
    if (r - l == 1) {
        query(r);
        query(l);
        if (val == 1) return l;
        else          return r;
    }

    if (r - l == 2) {
        query(r);
        query(l);
        if (val == 0) return l+1;
        else if (val==1) return l;
        else return r;
    }

    if (r - l == 3) {
        query(r-1);
        query(l+1);
        if (val == 1) {
            query(l);
            if (val == 1) return l;
            else return l+1;
        } else {
            query(r);
            if (val == 1) return r;
            else return r-1;
        }
    }

    if (r - l == 4) {
        query(r-1);
        query(l+1);
        if (val == 1) {
            query(l);
            if (val == 1) return l;
            else return l+1;
        } else {
            query(r);
            query(r-1);
            if (val == 1) return r-1;
            else return r;
        }
    }

    if (r - l == 5) {
        query(r-2);
        query(l+2);
        if (val == 1) {
            query(l);
            if (val == 1) return l;
            else return l+2;
        } else {
            query(r);
            if (val == 1) {
                query(r-1);
                if (val == 1) return r-1;
                else return r;
            } else {
                return (r-2);
            }
        }
    }

    return 0;
}

int
HC(int _n)
{
    n = _n;
    int r, l;
    int val, last = -1;
    int tr,tl;

    l = 1;
    r = _n;

    if (r - l < 2) return specialcase(last, l,r);
    int mid = (r+l+1)>>1;
    tl = mid;
    tr = mid+1;
    query(tl);
    query(tr);

    if (val == 1)
        l = (tl+tr+2)>>1;
    else
        r = (tl+tr-1)>>1;


    while (l < r) {
        /* if (r - l < 2) return specialcase(last, l,r); */
        mid = (r+l+1)>>1;
        /* cout << last << ' ' << r << ' ' << l << ' ' << mid << endl; */
        tl = last;
        if (tl >= r) {
            tr = l + (r-last);
            tr = max(tr,1);
            query(tr);
            if (val==1)
                r = (tl+tr-1)>>1;
            else
                l = (tl+tr+2)>>1;
        } else {
            tr = r + (l-last);
            tr = min(tr,n);
            query(tr);
            if (val==1)
                l = (tl+tr+2)>>1;
            else
                r = (tl+tr-1)>>1;
        }
    }

    return l;
}

#ifdef ONPC
int
check(int x, int r)
{
    cnt = 0;
    LAST = -1;
    R = r;
    /* cout << HC(x) << endl; */
    return HC(x);
}

void
solve()
{
    int _n, _y;
    cin >> _n;
    cin >> _y;
    int mval = _n * 3;
    mval = 31-__builtin_clz(mval);
    int val = check(_n,_y);
    cout << _n << ' ' << val << endl;
    #ifndef ONTST
        cout << "VALS: " << _n << ' ' << _y << ' ' << mval << endl;
        cout << "ANS: " << val << ' ' << cnt << endl;
    #endif
}

int32_t
main()
{
    #ifndef ONTST
        freopen("in", "r", stdin);
    #endif
    int t = 1;
    while(t--)
        solve();
}
#endif

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 5 / 25