Submission #358523

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
358523	2021-01-25T16:29:53 Z	idk321	Hotter Colder (IOI10_hottercolder)	C++11	83 / 100	684 ms	15664 KB

hottercolder

    #include "grader.h"
     
    #include <bits/stdc++.h>
    using namespace std;
     
    int HC(int n){
      	if (n == 1) return 1;
        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:109:13: warning: unused variable 'q1' [-Wunused-variable]
  109 |         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

8.0 / 25.0

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