NEERC/central/central_gk.java

   1 import java.util.*;
   2 import java.io.*;
   3 import static java.lang.System.out;
   4
   5 class central_gk {
   6     static Scanner in;
   7     static final int UNDEFINED = -1;
   8
   9     int ask(int i, int j, int k) {
  10         out.println((i + 1) + " " + (j + 1) + " " + (k + 1));
  11         out.flush();
  12         return in.nextInt();
  13     }
  14
  15     Queue<Integer> decide(int[] a, int l, Queue<Integer> queue) {
  16         while (queue.size() > 2) {
  17             int x = queue.poll();
  18             int y = queue.poll();
  19             int z = queue.poll();
  20
  21             int za = ask(l, x, y);
  22             int xa = ask(l, y, z);
  23             int ya = ask(l, z, x);
  24
  25             if (xa == ya) {
  26                 a[z] = xa;
  27                 queue.add(x);
  28                 queue.add(y);
  29             }
  30             if (ya == za) {
  31                 a[x] = ya;
  32                 queue.add(y);
  33                 queue.add(z);
  34             }
  35             if (za == xa) {
  36                 a[y] = za;
  37                 queue.add(z);
  38                 queue.add(x);
  39             }
  40         }
  41         return queue;
  42     }
  43
  44     Queue<Integer> take(int[] a, int value) {
  45         Queue<Integer> result = new LinkedList<Integer>();
  46         for (int i = 0; i < a.length; i++) {
  47             if (a[i] == value) {
  48                 result.add(i);
  49             }
  50         }
  51         return result;
  52     }
  53
  54     int[] askAll(int n, int l, int r) {
  55         int[] a = new int[n];
  56         for (int i = 0; i < n; i++) {
  57             a[i] = (i == l || i == r) ? UNDEFINED : ask(l, r, i);
  58         }
  59         return a;
  60     }
  61
  62     void run() throws IOException {
  63         int n = in.nextInt();
  64         if (n == 3) {
  65             out.println("OK 1 2 3");
  66             return;
  67         }
  68
  69         for (int j = 1; j < n; j++) {
  70             int[] a = askAll(n, 0, j);
  71
  72             int min = UNDEFINED;
  73             int max = UNDEFINED;
  74             for (int i = 0; i < n; i++) {
  75                 if (min == UNDEFINED && a[i] != UNDEFINED || min > a[i]) {
  76                     min = a[i];
  77                 }
  78                 if (max == UNDEFINED && a[i] != UNDEFINED || max < a[i]) {
  79                     max = a[i];
  80                 }
  81             }
  82
  83             if (min == max) {
  84                 Queue<Integer> other = decide(a, 0, take(a, max));
  85                 if (max == 2) {
  86                     a[0] = 1;
  87                     a[j] = 2;
  88                     a[other.remove()] = n - 1;
  89                     a[other.remove()] = n;
  90                 } else {
  91                     a[other.remove()] = 1;
  92                     a[other.remove()] = 2;
  93                     a[0] = n;
  94                     a[j] = n - 1;
  95                 }
  96             } else {
  97                 Queue<Integer> less = decide(a, 0, take(a, min));
  98                 Queue<Integer> greater = decide(a, 0, take(a, max));
  99                 int l = less.remove();
 100                 int r = greater.remove();
 101                 if (!less.isEmpty()) {
 102                     int p = less.remove();
 103                     if (p != 0 && p != j) {
 104                         a[p] = 2;
 105                     }
 106                 }
 107                 if (!greater.isEmpty()) {
 108                     int p = greater.remove();
 109                     if (p != 0 && p != j) {
 110                         a[p] = n - 1;
 111                     }
 112                 }
 113
 114                 a[l] = 1;
 115                 a[r] = n;
 116                 if (a[0] == UNDEFINED) {
 117                     a[0] = ask(l, r, 0);
 118                 }
 119                 if (a[j] == UNDEFINED) {
 120                     a[j] = ask(l, r, j);
 121                 }
 122             }
 123
 124             out.print("OK");
 125             for (int i : a) {
 126                 out.print(" " + i);
 127             }
 128             out.println();
 129             return;
 130         }
 131     }
 132
 133     public static void main(String[] args) throws Exception {
 134         in = new Scanner(System.in);
 135
 136         new central_gk().run();
 137
 138         in.close();
 139         out.close();
 140     }
 141 }