Non-Interactive Guessing Number (Problem C, 2017 ICPC Asia Jakarta Regional Contest, 2017)
Time limit: 0.5 sec
Memory limit: 256MB
Author: Ammar Fathin Sabili

# Problem Statement

*Romanos: "Can I submit an interactive problem to ACM-ICPC 2017 Jakarta?"  
Theodora: "No."  
Romanos: "Aww, man.. That's not fun."*

Then Romanos decided to submit a non-interactive version of his problem to the contest; and here it is, based on his playing with Theodora.

Romanos and Theodora are playing a game. Initially, Theodora picks a number between $1$ to $N$ inclusive. Romanos' goal is to determine that number. He can make up to $K$ guesses. For each guess, he will say a number out loud as his guess. Theodora will then say one of the following answers based on the exact condition:
- "My number is smaller than your guess ($<$)",
- "My number is greater than your guess ($>$)", or
- "Your guess is correct ($=$)".

The game will end right after one of the following:
- Romanos guesses the correct number (he wins), or
- All $K$ guesses are wrong (he loses).

Sadly, Romanos is not playing the game seriously. He knows the best strategy to win this game, but he does not always use it. Nevertheless, he pretends that he plays seriously, hence his guess will never be a dumb one. In other words, his guess will always be a number between $1$ to $N$ inclusive and will always be consistent with all of Theodora's previous answers.

For example, suppose $N$ is $10$ and Romanos' first guess is $4$. If Theodora answers "My number is smaller than your guess ($<$)" then the next Romanos's guess will always be between $1$ to $3$, inclusive.

Contrast to Romanos, Theodora is playing the game too seriously. She wants to win (by making Romanos lose) and "cheats" as follows.

Adaptively, Theodora might change her number as far as it is consistent with all of her previous answers. To do that, whenever possible, Theodora will always answer either "My number is smaller than your guess ($<$)" or "My number is greater than your guess ($>$)" that maximizes the possible answer range. In the case of tie, she will always answer the first one ($<$).

For example, suppose $N = 10$ and Romanos' first guess is $4$. Theodora will always answer "My number is greater than your guess ($>$)" because the possible answer range will be between $5$ to $10$ inclusive; it is larger than $1$ to $3$ inclusive.

Now, this is the actual problem proposed by Romanos. You are given $N$, $K$, and Theodora's answer for each guess. Can you show one of the possible scenario for Romanos' guesses or state that it is impossible?

# Input

The first line contains two integers: $N$ $K$ ($1 \leq N \leq 10^{18};\ 1 \leq K \leq 50{,}000$) in a line denoting the number range and the number of guesses.  
The second line contains a string in a line denoting Theodora's answers.  
Each character of the string is either `<`, `>`, or `=`, and either:
- The last character of the string is `=` and each character of the string other than the last character is either `<` or `>`, and the length of the string is not more than $K$, **or**
- The length of the string is exactly $K$ and each character of the string is either `<` or `>`.

# Output

- If there is a possible scenario for Romanos' guesses, the output contains $M$ integers: $A_1\ A_2\ \cdots\ A_M$ in a line denoting Romanos' guesses where $M$ is the length of the string and $A_i$ is Romanos' $i$-th guess. If there are more than one possible scenario for Romanos' guesses, you may output any of them.
- If there is no possible scenario for Romanos' guesses, just output `-1` in a line.

# Sample Input
```
10 5
><>=
```
# Output for Sample Input
```
5 8 6 7
```
# Sample Input
```
10 5
><<><
```
# Output for Sample Input
```
4 10 8 5 7
```
# Sample Input
```
10 5
<>=
```
# Output for Sample Input
```
-1
```
# Sample Input
```
10 9
>>>>>>>>
```
# Output for Sample Input
```
1 2 3 4 5 6 7 8 9
```
# Sample Input
```
10 10
>>>>>>>>>>
```
# Output for Sample Input
```
-1
```

Sample inputs:
10 5
><>=

10 5
><<><

10 5
<>=

10 9
>>>>>>>>>

10 10
>>>>>>>>>>

Sample outputs:
5 8 6 7

1 10 9 2 8

-1

1 2 3 4 5 6 7 8 9

-1

# Solution Analysis
Analysis author: Ammar Fathin Sabili

Let's start with the fact that the value of $K$ in input is not important at all. Let $L$ be the length of the string instead.

There are some trivial (or tricky?) cases:
- If the string ends with '=' and $L > N$, then there is no solution.
- If the string doesn't end with '=' and $L \geq N$, then there is no solution.
- If the string doesn't end with '=' and $L < N$, then there is a simple solution: one by one from the first to last character, output the largest possible number if it is '<' or smallest possible number if it is '>'. For example, $N = 10$ and $S = \texttt{"><><>"}$ will construct $1 \sim 10 \sim 9 \sim 2 \sim 8$.

The main problem is how to construct a solution given that the string ends with '=' and $L \leq N$, means that Romanos has to win on exactly the $L$-th turn given the scenario of the string. It is provable that if Romanos is actually able to win on $X$-th turn, then he can make himself win on $Y$-th turn where $X \leq Y \leq L$. Hence, we can simulate the best strategy to find out if Romanos can win on the $L$-th turn; which is the binary search strategy.

Let boolean function $\texttt{isPossible}(A, B, \texttt{pos})$ be the function returning if it is possible to construct a solution given that the smallest and largest possible numbers are $A$ and $B$ respectively and now we're on the $\texttt{pos}$-th turn (of $L$, 0-indexed). Based on previous proof, binary search can be used for this function. Let's call the number used to guess is $\texttt{mid}$; if the $\texttt{pos}$-th character is '<' then the number of numbers less than $\texttt{mid}$ has to $\leq$ the number of numbers more than $\texttt{mid}$, else (if the character is '>') then the number of numbers less than $\texttt{mid}$ has to $>$ the number of numbers more than $\texttt{mid}$. It turns out the value of $\texttt{mid}$ is $\left\lfloor\frac{A + B + 1}{2}\right\rfloor$ if '<' or $\left\lfloor\frac{A + B - 1}{2}\right\rfloor$ if '>'. The algorithm will be like this:

```
bool isPossible(long long A, long long B, int pos) {
    if (A == B) return true;
    if (S[pos] == '=') return false;

    if (S[pos] == '<') {
        long long mid = (A + B + 1) / 2;
        return isPossible(A, mid-1, pos+1);
    } else {
        long long mid = (A + B - 1) / 2;
        return isPossible(mid+1, B, pos+1);
    }
}
```
Calling $\texttt{isPossible}(1, N, 0)$ will check if there exists a solution, but how can we construct the solution? There are actually two strategies that can be used by Romanos on each turn: using best strategy which is using binary search, or the "nonsense" one which is "the largest possible number if it is '<' or smallest possible number if it is '>'". Those two strategies are working dependently: in case Romanos needs to guess fast ($L$ is small) he needs first strategy, or in case of need to guess slow but sure ($L$ is large) he needs second strategy. To not making the game ends faster than $L$ turns, Romanos always chooses the second strategy whenever possible. These strategies are sufficient to construct one of possible solution.

Let $\texttt{solve}(A, B, \texttt{pos})$ be the procedure to construct a solution given that the smallest and largest possible numbers are $A$ and $B$ respectively and now we're on the $\texttt{pos}$-th turn (of $L$, 0-indexed). Calling $\texttt{solve}(1, N, 0)$ will do. The algorithm will be like this:
```
void solve(long long A, long long B, int pos) {
    if (S[pos] == '=') {
        guess(A);
    } else if (S[pos] == '<' && isPossible(A, B-1, pos+1)) {
        guess(B);
        solve(A, B-1, pos+1);
    } else if (S[pos] == '<') {
        long long mid = (A + B + 1) / 2;
        guess(mid);
        solve(A, mid-1, pos+1);
    } else if (S[pos] == '>' && isPossible(A+1, B, pos+1)) {
        guess(A);
        solve(A+1, B, pos+1);
    } else if (S[pos] == '>') {
        long long mid = (A + B - 1) / 2;
        guess(mid);
        solve(mid+1, B, pos+1);
    }
}
```

Special judge (C++ scorer):
#include <bits/stdc++.h>
using namespace std;

int wa() {
    cout << "WA" << endl;
    return 0;
}

int ac() {
    // cout << "AC" << endl;
    return 0;
}

long long N, K;
string S;
vector<long long> KEY_ANS, con;

int check(int id, long long left, long long right) {
	if (id == K) return ac();
	long long x = con[id];
	
	if (x < left || x > right) return wa();
	if (left == right) {
		if (S[id] == '=') return ac();
		return wa();
	}
	if (x - left >= right - x) {
		if (S[id] != '<') return wa();
		return check(id+1, left, x-1);
	} else {
		if (S[id] != '>') return wa();
		return check(id+1, x+1, right);
	}
}

int checks(istream& tc_in, istream& tc_out, istream& con_out) {
  tc_in >> N >> K;
  tc_in >> S;
  K = S.length();
  
  long long x;
    while (tc_out >> x) KEY_ANS.push_back(x);
  while (con_out >> x) con.push_back(x);
  
  if (KEY_ANS.size() != con.size()) return wa();
  if (KEY_ANS[0] == -1) {
    if (con[0] == -1) return ac();
    return wa();
  }
  
  return check(0, 1LL, N);
}

int main(int argc, char* argv[]) {
  ifstream tc_in(argv[1]);
  ifstream tc_out(argv[3]);

	return checks(tc_in, tc_out, cin);
}