79 lines
1.5 KiB
Java
79 lines
1.5 KiB
Java
package chelper;
|
|
|
|
import java.util.Arrays;
|
|
import java.util.LinkedList;
|
|
import java.util.Queue;
|
|
|
|
import io.InputReader;
|
|
import io.OutputWriter;
|
|
|
|
public class M {
|
|
boolean ask(InputReader in, OutputWriter out, int i, int j) {
|
|
out.println("? " + i + " " + j);
|
|
out.flush();
|
|
return in.nextLine().charAt(0) == '<';
|
|
}
|
|
|
|
public void solve(int testNumber, InputReader in, OutputWriter out) {
|
|
int n = Integer.parseInt(in.nextLine());
|
|
|
|
int m = Integer.highestOneBit(n) * 2;
|
|
int[] a = new int[2 * m];
|
|
Arrays.fill(a, -1);
|
|
|
|
for (int i = 0; i < n; i++) {
|
|
a[m + i] = i + 1;
|
|
}
|
|
|
|
for (int i = m - 1; i >= 1; i--) {
|
|
int c1 = a[2 * i];
|
|
int c2 = a[2 * i + 1];
|
|
|
|
if (c2 == -1 || c1 == -1) {
|
|
a[i] = c1;
|
|
continue;
|
|
}
|
|
|
|
a[i] = ask(in, out, c1, c2) ? c2 : c1;
|
|
}
|
|
|
|
int p = 1;
|
|
|
|
Queue<Integer> candidates = new LinkedList<>();
|
|
|
|
while (true) {
|
|
int c1 = p * 2;
|
|
int c2 = p * 2 + 1;
|
|
|
|
if (c1 >= 2 * m || c2 >= 2 * m) {
|
|
break;
|
|
}
|
|
|
|
if (a[c2] == a[p]) {
|
|
int t = c1;
|
|
c1 = c2;
|
|
c2 = t;
|
|
}
|
|
|
|
if (a[c2] != -1) {
|
|
candidates.add(a[c2]);
|
|
}
|
|
p = c1;
|
|
}
|
|
|
|
while (candidates.size() > 1) {
|
|
int a1 = candidates.poll();
|
|
int a2 = candidates.poll();
|
|
|
|
if (ask(in, out, a1, a2)) {
|
|
candidates.add(a2);
|
|
} else {
|
|
candidates.add(a1);
|
|
}
|
|
}
|
|
|
|
out.println("! " + candidates.poll());
|
|
out.flush();
|
|
}
|
|
}
|