oj.uz

답안 #574093

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
574093 2022-06-07T18:57:38 Z MadokaMagicaFan Hotter Colder (IOI10_hottercolder) C++14
82 / 100
 552 ms 8104 KB 
#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;
    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;

    l = 1;
    r = _n;

    int tl = (l+r)>>3;
    if (!tl)
        return specialcase(last,l,r);
    int tr = 3*tl;

    ask(tl);
    last = tl;
    query(tr);
    while (val == -1) {
        r = tl + ((tr - tl)>>1);
        if (l == r) return l;
        tl = (l+r)>>3;
        if (!tl)
            return specialcase(last,l,r);
        tr = 3*tl;
        query(tl);
        query(tr);
    }

    l = (tl+tr+2)>>1;

    while (1) {
        int mid = (l+r+1)>>1;
        if (l == r) return l;

        if (last < mid) {
            tr = r + (l-last);
        } else {
            tr = l + (r-last);
        }

        if (r - l < 6)
            return specialcase(last,l,r);

        tr = max(tr,1);
        tr = min(tr,n);

        tl = last;

        if (tl == tr) {
            query(l);
            continue;
        }
    #ifdef ONPC
    #ifndef ONTST
        cout << "SPECIAL: " << tl << ' ' << tr << ' ' << r << ' ' << l << endl;
    #endif
    #endif
        query(tr);

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



    return -1;
}

#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

Compilation message

hottercolder.cpp: In function 'int specialcase(int, int, int)':
hottercolder.cpp:127:9: warning: 'val' may be used uninitialized in this function [-Wmaybe-uninitialized]
  127 |         if (val == 1) {
      |         ^~
hottercolder.cpp: In function 'int HC(int)':
hottercolder.cpp:164:16: warning: 'val' may be used uninitialized in this function [-Wmaybe-uninitialized]
  164 |     while (val == -1) {
      |            ~~~~^~~~~

Subtask #1
25.0 / 25.0

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

Subtask #2
25.0 / 25.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
7.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 552 ms 8104 KB Output is partially correct - alpha = 0.285714285714