Submission #357799

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
357799	2021-01-24T17:27:40 Z	idk321	Hotter Colder (IOI10_hottercolder)	C++11	75 / 100	766 ms	8312 KB

hottercolder

#include "grader.h"

#include <bits/stdc++.h>
using namespace std;

int HC(int n){
    int a = 1;
    int b = n;
    int moves = 0;
    int pr = -1;
    while (b - 1 > a)
    {
        if (pr == -1)
        {
            int mid = (a + b) / 2;
            Guess(mid + 1);
            int q = Guess(mid);
            if (q == 1)
            {
                b = mid;
            } else
            {
                a = mid;
            }

            pr = mid;
            moves +=  2;
        } else
        {
            int mid = (a + b) / 2;
            int na1 = a;
            int nb1;
            int na2;
            int nb2 = b;
            if (b - a % 2 == 0)
            {
                nb1 = mid - 1;
                na2 = mid + 1;
            } else
            {
                nb1 = mid;
                na2 = mid + 1;
            }
            if (pr == a)
            {
                int q = Guess(b);
                if (q == 0)
                {
                    if ( (b - a) % 2 == 0) return mid;
                    a = mid;
                    b = mid + 1;
                    continue;
                }
                if (q == 1)
                {
                    a = na2;
                    b = nb2;
                } else
                {
                    a = na1;
                    b = nb1;
                }
            } else
            {
                int q = Guess(a);
                if (q == 0)
                {
                    if ( (b - a) % 2 == 0) return mid;
                    a = mid;
                    b = mid + 1;
                    continue;
                }
                if (q == 1)
                {
                    a = na1;
                    b = nb1;
                } else
                {
                    a = na2;
                    b = nb2;
                }
            }

            pr = -1;
            moves++;
            //cout << na1 << " " << nb1 << " " << na2 << " " << nb2 << endl;
        }
        //cout << a << " " << b << endl;
    }

    moves++;
    moves += pr == -1;

    if (pr != -1)
    {
        if (pr == a)
        {
            int q = Guess(b);
            if (q == 1) return b;
            return a;
        } else
        {
            int q = Guess(a);
            if (q == 1) return a;
            return b;
        }
    }
    int q1 = Guess(a);
    int q2 = Guess(b);

    if (q2 == 1) return b;
    return a;
}

//500000000 1


/*




187475896 80819041
395488598 62058616
247790495 86181240
388387015 93271952
104181931 53791873
351400605 113934373
*/

Compilation message

hottercolder.cpp: In function 'int HC(int)':
hottercolder.cpp:108:9: warning: unused variable 'q1' [-Wunused-variable]
  108 |     int q1 = Guess(a);
      |         ^~

Subtask #1

25.0 / 25.0

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

Subtask #2

25.0 / 25.0

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

Subtask #3

25.0 / 25.0

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

Subtask #4

0.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	766 ms	8312 KB	Output isn't correct - alpha = 0.000000000000