1847E - Triangle Platinum - CodeForces Solution

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

using LL = long long;

int Cal(int a, int b, int c) {
  if (a > b) swap(a, b);
  if (b > c) swap(b, c);
  if (a > b) swap(a, b);
  if (a + b <= c) return 0;
  int s = a + b + c;
  return s * (s - a - a) * (s - b - b) * (s - c - c);
}

int Query(int a, int b, int c) {
  cout << "? " << a + 1 << " " << b + 1 << " " << c + 1 << endl;
  int ans;
  cin >> ans;
  return ans;
}

int cnt = 0;
vector<int> ans;
int f[8][8][8];

bool Check(vector<int>& x) {
  int n = x.size();
  if (n <= 2) return true;
  for (int i = 0; i + 2 < n; ++i) {
    for (int j = i + 1; j + 1 < n; ++j) {
      if (f[i][j][n - 1] != Cal(x[i], x[j], x[n - 1])) return false;
    }
  }
  return true;
}

void Dfs(vector<int>& x, int p, int n) {
  if (p == n) {
    ++cnt;
    ans = x;
  }
  for (int i = 1; i <= 4; ++i) {
    x.push_back(i);
    if (Check(x)) Dfs(x, p + 1, n);
    if (cnt > 1) return;
    x.pop_back();
  }
}

int SolveSmall(int n) {
  for (int i = 0; i + 2 < n; ++i) {
    for (int j = i + 1; j + 1 < n; ++j) {
      for (int k = j + 1; k < n; ++k) {
        f[i][j][k] = Query(i, j, k);
      }
    }
  }
  vector<int> x;
  Dfs(x, 0, n);
  if (cnt > 1) {
    cout << "! -1" << endl;
  } else {
    cout << "! ";
    for (int a : ans) cout << a << " ";
    cout << endl;
  }
  return 0;
}

void Fill(vector<int>& ans, int a, int b, int* s) {
  for (int i = 0; i < ans.size(); ++i) {
    if (ans[i] == 0) {
      int val = Query(a, b, i);
      for (int l = 1; l <= 4; ++l) {
        if (val == s[l]) ans[i] = l;
      }
    }
  }
  cout << "!";
  for (int a : ans) cout << " " << a;
  cout << endl;
}

int main() {
  int n;
  cin >> n;
  if (n <= 8) return SolveSmall(n);
  int s[5];
  for (int i = 1; i <= 4; ++i) s[i] = Cal(i, i, i);
  vector<int> sa;
  for (int i = 0; i + 2 < 9; ++i) {
    for (int j = i + 1; j + 1 < 9; ++j) {
      for (int k = j + 1; k < 9; ++k) {
        int val = Query(i, j, k);
        for (int l = 1; l <= 4; ++l) {
          if (val == s[l]) {
            sa.push_back(l);
            sa.push_back(i);
            sa.push_back(j);
            sa.push_back(k);
          }
          if (!sa.empty()) break;
        }
        if (!sa.empty()) break;
      }
      if (!sa.empty()) break;
    }
    if (!sa.empty()) break;
  }
  vector<int> ans(n);
  ans[sa[1]] = ans[sa[2]] = ans[sa[3]] = sa[0];
  if (sa[0] != 1) {
    for (int i = 1; i <= 4; ++i) s[i] = Cal(sa[0], sa[0], i);
    Fill(ans, sa[1], sa[2], s);
  } else {
    vector<int> p;
    for (int i = 0; i < n; ++i) {
      if (ans[i] == 0) {
        int val = Query(sa[1], sa[2], i);
        if (val == 0) {
          p.push_back(i);
        } else {
          ans[i] = 1;
        }
      }
      if (p.size() == 4) break;
    }
    for (int i = 1; i <= 4; ++i) s[i] = Cal(1, i, i);
    if (p.size() == 4) {
      int one = sa[1];
      sa.clear();
      for (int i = 0; i + 1 < 4; ++i) {
        for (int j = i + 1; j < 4; ++j) {
          int val = Query(p[i], p[j], one);
          for (int l = 2; l <= 4; ++l) {
            if (val == s[l]) {
              sa.push_back(l);
              sa.push_back(p[i]);
              sa.push_back(p[j]);
            }
            if (!sa.empty()) break;
          }
          if (!sa.empty()) break;
        }
        if (!sa.empty()) break;
      }
      ans[sa[1]] = ans[sa[2]] = sa[0];
      for (int i = 1; i <= 4; ++i) s[i] = Cal(sa[0], sa[0], i);
      Fill(ans, sa[1], sa[2], s);
    } else 
    if (p.empty()) {
      cout << "!";
      for (int a : ans) cout << " " << a;
      cout << endl;
    } else
    if (p.size() == 1) {
      cout << "! -1" << endl;
    } else
    if (p.size() == 2) {
      int one = sa[1];
      for (int i = 1; i <= 4; ++i) {
        for (int j = 1; j <= 4; ++j) {
          if (Query(one, p[0], p[1]) == Cal(1, i, j)) {
            ++cnt;
            ans[p[0]] = i;
            ans[p[1]] = j;
          }
        }
      }
      if (cnt > 1) {
        cout << "! -1" << endl;
      } else {
        cout << "!";
        for (int a : ans) cout << " " << a;
        cout << endl;
      }
    } else {
      int one = sa[1];
      for (int i = 1; i <= 4; ++i) {
        for (int j = 1; j <= 4; ++j) {
          for (int k = 1; k <= 4; ++k) {
            if (Query(one, p[0], p[1]) == Cal(1, i, j) &&
                Query(one, p[0], p[2]) == Cal(1, i, k) &&
                Query(one, p[1], p[2]) == Cal(1, j, k) &&
                Query(p[0], p[1], p[2]) == Cal(i, j, k)) {
              ++cnt;
              ans[p[0]] = i;
              ans[p[1]] = j;
              ans[p[2]] = k;
            }
          }
        }
      }
      if (cnt > 1) {
        cout << "! -1" << endl;
      } else {
        cout << "!";
        for (int a : ans) cout << " " << a;
        cout << endl;
      }
    }
  }
  return 0;
}