結果

問題 No.3400 Nana's Plus Permutation Game (7 + 7) ÷ 7
コンテスト
ユーザー Kude
提出日時 2025-12-07 08:38:41
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 864 ms / 2,777 ms
コード長 6,735 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,023 ms
コンパイル使用メモリ 328,648 KB
実行使用メモリ 26,240 KB
平均クエリ数 13471.47
最終ジャッジ日時 2025-12-07 08:39:49
合計ジャッジ時間 62,341 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 77
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
namespace {
#pragma GCC diagnostic ignored "-Wunused-function"
#include<atcoder/all>
#pragma GCC diagnostic warning "-Wunused-function"
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }
template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; }
using ll = long long;
using P = pair<int,int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;

template<int element_size>
struct array_set {
  int state[element_size];  // -1 if not in set else index in elems
  int elems[element_size];
  int size = 0;
  array_set() { memset(state, -1, sizeof(int) * element_size); }
  void insert(int x) {
    if (state[x] == -1) {
      state[x] = size;
      elems[size] = x;
      size++;
    }
  }
  bool contains(int x) { return x >= 0 && state[x] != -1; }
  int* begin() { return elems; }
  int* end() { return elems + size; }
  void clear() { while(size) state[elems[--size]] = -1; }
  void erase(int x) {  // not tested
    int idx = state[x];
    if (idx != -1) {
      state[x] = -1;
      size--;
      if (idx != size) {
        int y = elems[size];
        state[y] = idx;
        elems[idx] = y;
      }
    }
  }
};

template<class T, int element_size>
struct array_map {
  int state[element_size];  // -1 if not in set else index in elems
  pair<int, T> elems[element_size];
  int size = 0;
  array_map() { memset(state, -1, sizeof(int) * element_size); }
  bool contains(int x) { return state[x] != -1; }
  pair<int, T>* begin() { return elems; }
  pair<int, T>* end() { return elems + size; }
  void clear() { while(size) state[elems[--size].first] = -1; }
  void erase(int x) {  // not tested
    int idx = state[x];
    if (idx != -1) {
      state[x] = -1;
      size--;
      if (idx != size) {
        int y = elems[size].first;
        state[y] = idx;
        elems[idx] = move(elems[size]);
      }
    }
  }
  T& operator[](int x) {
    if (state[x] == -1) {
      state[x] = size;
      elems[size].first = x;
      elems[size].second = T();
      size++;
    }
    return elems[state[x]].second;
  }
};

} int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    int n;
    cin >> n;
    VI p(n + 1, -1), pos(n + 1, -1);
    auto ask = [&](int i, int j) {
      cout << "1 " << i << ' ' << j << endl;
      int k;
      cin >> k;
      return k;
    };
    auto dfs = [&](auto&& self, VI idx) -> void {
      assert(idx.size() >= 4);
      int sz = idx.size();
      // S:={1, 2, ..., sz}
      // find a s.t. pa+pb in S in sz/2+1 queries
      static array_set<10002> st;
      st.clear();
      for (int i : idx) st.insert(i);
      int a = -1;
      for (int i = 0; i + 1 < ssize(idx); i += 2) {
        int k = ask(idx[i], idx[i+1]);
        if (st.contains(k)) {
          a = idx[i];
          idx.erase(idx.begin() + i);
          break;
        }
      }
      if (a == -1) {
        if (sz % 2) {
          a = idx.back();
          idx.pop_back();
        } else {
          // a+b = k+1, c+d = k+1, a,b,c,d distinct
          // => a+c <= k or b+d <= k
          int k = ask(idx[0], idx[2]);
          if (st.contains(k)) {
            a = idx[0];
            idx.erase(idx.begin());
          } else {
            a = idx[1];
            idx.erase(idx.begin() + 1);
          }
        }
      }
      vector<P> es;
      for (int i : idx) {
        int k = ask(i, a);
        if (st.contains(k)) es.emplace_back(i, k);
      }
      static array_map<int, 10002> to, indeg;
      to.clear(), indeg.clear();
      for (auto [u, v] : es) to[u] = v, indeg[v]++;
      vector<P> heads;
      for (int i : idx) if (!indeg[i]) {
        int j = i, l = 0;
        while (to[j]) l++, j = to[j];
        heads.emplace_back(i, l);
      }
      assert(heads.size());
      if (heads.size() == 1 && heads[0].second == sz - 2) {
        p[a] = 1;
        int i = heads[0].first;
        p[i] = 2;
        rep(c, sz - 2) i = to[i], p[i] = 3 + c;
        return;
      }
      if (ranges::max_element(heads, {}, &P::second)->second > 1) {
        heads.erase(ranges::min_element(heads, {}, &P::second));
      } else {
        heads.erase(ranges::remove_if(heads, [](P x) { return x.second == 0; }).begin(), heads.end());
      }
      if (heads.size() == 1) {
        int i1 = heads[0].first;
        p[i1] = 1;
        idx.emplace_back(a);
        auto dfs = [&](auto&& self, int i) -> void {
          if (p[i] != -1) return;
          int ni = ask(i1, i);
          if (st.contains(ni)) {
            self(self, ni);
            p[i] = p[ni] - 1;
          } else {
            p[i] = sz;
          }
        };
        for (int i : idx) dfs(dfs, i);
        return;
      }
      if (heads.size() <= 3) {
        assert(sz >= 5);
        int i12a, i12b, i3;
        if (heads.size() == 2) {
          i12a = heads[0].first, i12b = heads[1].first;
          i3 = ask(i12a, i12b);
        } else {
          int x = heads[0].first, y = heads[1].first, z = heads[2].first;
          tie(i12a, i12b, i3) = ask(x, y) == z ? tuple(x, y, z) : ask(y, z) == x ? tuple(y, z, x) : tuple(z, x, y);
        }
        int i45a = ask(i12a, i3), i45b = ask(i12b, i3);
        int i1, i2, i4, i5;
        tie(i1, i2, i4, i5) = ask(i12a, i45a) == i45b ? tuple(i12a, i12b, i45a, i45b) : tuple(i12b, i12a, i45b, i45a);
        p[i1] = 1, p[i2] = 2, p[i3] = 3, p[i4] = 4, p[i5] = 5;
      } else {
        VI is;
        for (auto [i, l] : heads) is.emplace_back(i);
        self(self, is);
      }
      idx.emplace_back(a);
      for (int i : idx) if (p[i] != -1) pos[p[i]] = i;
      int i1 = pos[1], ix = pos[2], x = 2;
      assert(i1 != -1 && ix != -1);
      while (ix != a) {
        if (pos[x+1] == -1) {
          int k = ask(i1, ix);
          p[k] = x + 1;
          pos[p[k]] = k;
        }
        x++;
        ix = pos[x];
      }
      to.clear();
      for (auto [u, v] : es) to[u] = v;
      ix = pos[2], x = 2;
      while (x != sz) {
        if (to[ix]) {
          int j = to[ix];
          p[j] = x + p[a];
          pos[p[j]] = j;
        }
        if (pos[x+1] == -1) {
          int k = ask(i1, ix);
          p[k] = x + 1;
          pos[p[k]] = k;
        }
        x++;
        ix = pos[x];
      }
    };
    VI all_idx;
    rep(i, n) all_idx.emplace_back(i + 1);
    dfs(dfs, all_idx);
    cout << 2;
    for (int i = 1; i <= n; i++) cout << ' ' << p[i];
    cout << endl;
  }
}
0