JOI '14 - Secret

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 9.0s
Memory limit: 512M

Problem type
Allowed languages
C, C++
Contest Day 2 - JOI Open Contest

Anna invented a secret binary operation \star. For non-negative integers x, y less than or equal to 1\,000\,000\,000, a non-negative integer x \star y less than or equal to 1\,000\,000\,000 is determined. This operation \star is associative. Namely, the equality (x\star y)\star z = x\star (y\star z) holds for non-negative integers x, y, z less than or equal to 1\,000\,000\,000. This value is simply denoted by x \star y \star z.

Anna planned to play a game with Bruno. She asked him to guess the operation \star. She showed N integers A_0, A_1, \dots, A_{N - 1} to him. She gave to him a number of queries of the following form: "What is the value of A_L \star A_{L+1} \star \dots \star A_R?"

Bruno said it is difficult to play this game without hints. Anna decided to give hints to him. Each hint is given as follows: he will choose x, y to ask the value of x \star y, and she will tell him the value of x \star y. He can ask for hints when the integers A_0, A_1, \dots, A_{N-1} are given in the beginning of the game. He can also ask for hints when she gives a query to him. Of course, he would like to reduce the number of hints. Because he would like to behave as if he knows almost everything about the operation \star, he would especially like to reduce the number of hints after a query is given to him.

Task

Write a program which implements Bruno's strategy to ask for hints and answer Anna's queries correctly.

Implementation Details

You should write a program which implements the strategy to ask for hints and answer Anna's queries. Your program should include the header file secret.h by #include "secret.h"

Your program should implement the following procedures.

  • void Init(int N, int A[])
    

    This procedure is called only once in the beginning. The parameter N is the number N of the integers shown by Anna. The parameter A is an array of length N. The elements A[0], A[1], \dots, A[N-1] are the integers A_0, A_1, \dots, A_{N-1} shown by her.

  • int Query(int L, int R)
    

    This procedure is called when Anna gives a query to Bruno. This means she is asking the value of A_L \star A_{L+1} \star \dots \star A_R (0 \le L \le R \le N - 1).

The following procedure can be called by your program.

  • int Secret(int X, int Y)
    
    This procedure is called when Bruno asks for a hint. This means he is asking about the value of X \star Y. The parameters X and Y should be integers satisfying 0 \le X \le 1\,000\,000\,000 and 0 \le Y \le 1\,000\,000\,000. If this procedure is called with parameters not satisfying this condition, your program is considered as Wrong Answer [1] and terminated.

    This procedure returns the value of X \star Y.

Constraints

All input data satisfy the following conditions.

  • 1 \le N \le 1\,000.
  • 0 \le A_i \le 1\,000\,000\,000 (0 \le i \le N - 1).
  • The number of calls to Query is less than or equal to 10\,000.

Grading

The score will be given to your program if your program terminates successfully for each test case, it is not considered as Wrong Answer [1], and it returns the correct value for each call to Query.

Your score is calculated as follows.

  1. Your score is 100 if the following two conditions are satisfied for each test case:
    • In Init, the number of calls to Secret is less than or equal to 8\,000.
    • In each call to Query, the number of calls to Secret is less than or equal to 1.
  2. Your score is 30 if your program does not satisfy (1), and the following two conditions are satisfied:
    • In Init, the number of calls to Secret is less than or equal to 8\,000.
    • In each call to Query, the number of calls to Secret is less than or equal to 20.
  3. Your score is 6 if your program does not satisfy (1) or (2).

Comments


  • 1
    JeffreyZ  commented on Feb. 20, 2015, 9:59 p.m.

    There aren't any partial points for this question. Does this mean that we have to get a score of 100 to AC?


    • 0
      FatalEagle  commented on Feb. 20, 2015, 10:28 p.m.

      It was an oversight. Partial points are now enabled.


      • 0
        JeffreyZ  commented on Feb. 20, 2015, 10:45 p.m.

        I'm getting this error:

        In file included from joi14p6_submission.cpp:1:0: secret.h:2:17: fatal error: jni.h: No such file or directory

        include <jni.h>


        • 0
          FatalEagle  commented on Feb. 20, 2015, 10:50 p.m.

          It should work now. Try resubmitting.


        • 0
          Xyene  commented on Feb. 20, 2015, 10:47 p.m.

          Yea, sorry. Was hacking around trying to get signature grading to work for Java and I accidentally javah'd and overwrote the secret.h with a JNI header.


        • 0
          JeffreyZ  commented on Feb. 20, 2015, 10:46 p.m.

          Am I including secret.h incorrectly?


        • 1
          FatalEagle  commented on Feb. 20, 2015, 10:46 p.m.

          Xyene is attempting to add Java.

          Attempting.

          This will be resolved soon, sorry for the inconvenience.


          • 0
            JeffreyZ  commented on Feb. 20, 2015, 10:46 p.m.

            Ok, thank you!


            • 0
              FatalEagle  commented on Feb. 20, 2015, 10:47 p.m.

              By the way, you shouldn't wrap up the functions in a struct. Having them in global namespace should work.