NEERC/central/central_md.java

   1 import java.io.*;
   2 import java.util.*;
   3
   4 public class central_md {
   5         private static Scanner in;
   6         private static PrintWriter out;
   7
   8         private int ask() {
   9                 return in.nextInt();
  10         }
  11
  12         private int ask(int a, int b, int c) {
  13                 out.println((a + 1) + " " + (b + 1) + " " + (c + 1));
  14                 out.flush();
  15                 return in.nextInt();
  16         }
  17
  18         private void ok() {
  19                 out.print("OK");
  20                 for (int i = 0; i < n; i++) {
  21                         out.print(" " + value[i]);
  22                 }
  23                 out.println();
  24                 out.flush();
  25         }
  26
  27         int n;
  28         int[] value;
  29         int a, b;
  30         int low, high;
  31
  32         public void run() {
  33                 n = ask();
  34                 value = new int[n];
  35                 if (n >= 6) {
  36                         solveLarge();
  37                 } else {
  38                         solveSmall();
  39                 }
  40                 ok();
  41         }
  42
  43         private void solveLarge() {
  44                 findAB();
  45                 List<Integer> small = new ArrayList<Integer>();
  46                 List<Integer> large = new ArrayList<Integer>();
  47                 for (int i = 0; i < n; i++) {
  48                         if (i == a || i == b) {
  49                                 continue;
  50                         }
  51                         if (value[i] == low) {
  52                                 small.add(i);
  53                         } else if (value[i] == high) {
  54                                 large.add(i);
  55                         }
  56                 }
  57                 value[a] = ask(small.get(0), large.get(0), a);
  58                 value[b] = value[a] ^ low ^ high;
  59                 process(small, 1, 2);
  60                 process(large, n - 1, n);
  61         }
  62
  63         private void findAB() {
  64                 for (a = 0; a < 10 && a + 1 < n; a += 2) {
  65                         b = a + 1;
  66                         if (tryAB()) return;
  67                 }
  68                 for (a = 0; a < 6; a++) {
  69                         for (b = a + 1; b < 6; b++) {
  70                                 if (tryAB()) return;
  71                         }
  72                 }
  73         }
  74
  75         private boolean tryAB() {
  76                 low = n + 1;
  77                 high = 0;
  78                 int lowCount = 0;
  79                 int highCount = 0;
  80                 for (int i = 0; i < n; i++) {
  81                         if (i == a || i == b) {
  82                                 continue;
  83                         }
  84                         value[i] = ask(a, b, i);
  85                         if (value[i] < low) {
  86                                 low = value[i];
  87                                 lowCount = 1;
  88                         } else if (value[i] == low) {
  89                                 lowCount++;
  90                         }
  91                         if (value[i] > high) {
  92                                 high = value[i];
  93                                 highCount = 1;
  94                         } else if (value[i] == high) {
  95                                 highCount++;
  96                         }
  97                 }
  98                 return low != high && lowCount > 1 && highCount > 1;
  99         }
 100
 101         private void process(List<Integer> cells, int rest1, int rest2) {
 102                 while (cells.size() >= 3) {
 103                         int x = cells.get(cells.size() - 3);
 104                         int y = cells.get(cells.size() - 2);
 105                         int z = cells.get(cells.size() - 1);
 106                         int xy = ask(x, y, a);
 107                         int xz = ask(x, z, a);
 108                         int yz = ask(y, z, a);
 109                         int cell, val, index;
 110                         if (xy == xz) {
 111                                 cell = x;
 112                                 val = xy;
 113                                 index = cells.size() - 3;
 114                         } else if (xy == yz) {
 115                                 cell = y;
 116                                 val = xy;
 117                                 index = cells.size() - 2;
 118                         } else {
 119                                 cell = z;
 120                                 val = xz;
 121                                 index = cells.size() - 1;
 122                         }
 123                         value[cell] = val;
 124                         cells.remove(index);
 125                 }
 126                 value[cells.get(0)] = rest1;
 127                 value[cells.get(1)] = rest2;
 128         }
 129
 130         private void solveSmall() {
 131                 for (int i = 0; i < n; i++) {
 132                         for (int j = i + 1; j < n; j++) {
 133                                 for (int k = j + 1; k < n; k++) {
 134                                         int v = ask(i, j, k);
 135                                         value[i] += v;
 136                                         value[j] += v;
 137                                         value[k] += v;
 138                                 }
 139                         }
 140                 }
 141                 List<Integer> list = new ArrayList<Integer>();
 142                 for (int i = 0; i < n; i++) {
 143                         value[i] = n * value[i] + i;
 144                         list.add(value[i]);
 145                 }
 146                 Collections.sort(list);
 147                 for (int i = 0; i < n; i++) {
 148                         value[i] = list.indexOf(value[i]) + 1;
 149                 }
 150         }
 151
 152         public static void main(String[] args) {
 153                 Locale.setDefault(Locale.US);
 154                 in = new Scanner(System.in);
 155                 out = new PrintWriter(System.out);
 156                 new central_md().run();
 157                 in.close();
 158                 out.close();
 159         }
 160 }