結果
| 問題 | No.3400 Nana's Plus Permutation Game (7 + 7) ÷ 7 |
| コンテスト | |
| ユーザー |
 テナガザル
|
| 提出日時 | 2025-12-07 23:00:09 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.89.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 6,859 bytes |
| 記録 | |
| コンパイル時間 | 1,714 ms |
| コンパイル使用メモリ | 119,044 KB |
| 実行使用メモリ | 26,368 KB |
| 平均クエリ数 | 28083.21 |
| 最終ジャッジ日時 | 2025-12-07 23:01:16 |
| 合計ジャッジ時間 | 67,469 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | WA * 51 RE * 26 |
ソースコード
#include <iostream>
#include<vector>
#include <algorithm>
using namespace std;
void solve()
{
int n;
cin >> n;
vector<int> p(n, -1);
for (int i = 1; i < n; ++i)
{
cout << 1 << ' ' << 1 << ' ' << i + 1 << endl;
int k;
cin >> k;
--k;
if (k >= 0) p[k] = i;
}
int cnt = 0;
for (int i = 0; i < n; ++i) if (p[i] == -1) ++cnt;
auto cal = [&](vector<int> &a) -> int
{
vector<int> check = a;
for (int i = 0; i < n; ++i)
{
if (a[i] < 0) continue;
else if (a[a[i]] == -1) check[a[i]] = a[i];
}
int tmp = 0, cp = 0;
for (int i = 0; i < n; ++i)
{
cp += (a[i] == -1);
tmp += (check[i] == -1);
}
if (cp != (n + 1) / 2) return n - cp - (cp < (n + 1) / 2);
else return (tmp == 2 ? n / 2 : (n + 1) / 2);
};
auto calp = [&](int id, int c) -> void
{
vector<int> to(n, -1);
for (int i = 0; i < n; ++i) if (p[i] != -1) to[p[i]] = i;
int tid = -1, mi = n + 1;
for (int i = 0; i < n; ++i)
{
if (i != id && p[i] == -1)
{
int now = i, tmp = 0;
while (now != -1)
{
now = to[now];
++tmp;
}
if (tmp < mi)
{
mi = tmp;
tid = i;
}
}
}
if (c * 2 <= n) p[tid] = id;
};
vector<int> ans(n, -1);
if (cnt == n)
{
p.assign(n, -1);
vector<vector<pair<int, int>>> g(n);
int id1 = 1, id2 = 1;
for (int i = 2; i < n; ++i)
{
cout << 1 << ' ' << id1 + 1 << ' ' << i + 1 << endl;
int k;
cin >> k;
if (k == 1) id2 = i;
--k;
if (k >= 0) p[k] = i;
}
cnt = cal(p);
calp(id1, cnt);
for (int i = 0; i < n; ++i)
{
if (p[i] != -1)
{
g[p[i]].push_back({i, cnt});
g[i].push_back({p[i], -cnt});
}
}
p.assign(n, -1);
for (int i = 1; i < n; ++i)
{
if (i == id2) continue;
cout << 1 << ' ' << id2 + 1 << ' ' << i + 1 << endl;
int k;
cin >> k;
--k;
if (k >= 0) p[k] = i;
}
cnt = cal(p);
calp(id2, cnt);
for (int i = 0; i < n; ++i)
{
if (p[i] != -1)
{
g[p[i]].push_back({i, cnt});
g[i].push_back({p[i], -cnt});
}
}
auto dfs = [&](auto f, int now) -> void
{
for (auto [to, c] : g[now])
{
if (ans[to] == -1)
{
ans[to] = ans[now] + c;
f(f, to);
}
}
};
ans[0] = n;
dfs(dfs, 0);
}
else
{
int bs = 0;
cnt = cal(p);
calp(bs, cnt);
vector<int> id;
if (cnt <= 2)
{
for (int i = 0; i < n; ++i) if (p[i] == -1) id.push_back(i);
vector<int> to(n, -1);
for (int i = 0; i < n; ++i) if (p[i] != -1) to[p[i]] = i;
if (id.size() == 1)
{
int now = id[0], v = 1;
while (now != -1)
{
ans[now] = v;
now = to[now];
++v;
}
}
else if (id.size() == 2)
{
int now = id[0], tmp = 0;
while (now != -1)
{
now = to[now];
++tmp;
}
if (tmp == n / 2) swap(id[0], id[1]);
now = id[0];
int v = 1;
while (now != -1)
{
ans[now] = v;
v += 2;
now = to[now];
}
now = id[1], v = 2;
while (now != -1)
{
ans[now] = v;
v += 2;
now = to[now];
}
}
}
else
{
for (int i = 1; i < n; ++i) if (p[i] == -1) id.push_back(i);
while (id.size() > 1)
{
bs = id[0];
for (auto v : id)
{
if (v == bs) continue;
cout << 1 << ' ' << bs + 1 << ' ' << v + 1 << endl;
int k;
cin >> k;
if (k == -1) continue;
p[k - 1] = v;
}
vector<int> nid;
for (auto v : id)
{
if (v == bs) continue;
if (p[v] != -1 && p[p[v]] == -1 && p[v] != bs) nid.push_back(p[v]);
}
swap(nid, id);
}
p.assign(n, -1);
for (int i = 0; i < n; ++i)
{
if (i == bs) continue;
cout << 1 << ' ' << bs + 1 << ' ' << i + 1 << endl;
int k;
cin >> k;
if (k < 0) continue;
p[k - 1] = i;
}
cnt = cal(p);
calp(bs, cnt);
vector<int> to(n, -1);
for (int i = 0; i < n; ++i) if (p[i] != -1) to[p[i]] = i;
int tmp = 0;
id.clear();
for (int i = 0; i < n; ++i) if (p[i] == -1) id.push_back(i);
if (id.size() == 1)
{
int now = id[0], v = 1;
while (now != -1)
{
ans[now] = v;
now = to[now];
++v;
}
}
else
{
int now = id[0], tmp = 0;
while (now != -1)
{
now = to[now];
++tmp;
}
if (tmp == n / 2) swap(id[0], id[1]);
now = id[0];
int v = 1;
while (now != -1)
{
ans[now] = v;
v += 2;
now = to[now];
}
now = id[1], v = 2;
while (now != -1)
{
ans[now] = v;
v += 2;
now = to[now];
}
}
}
}
cout << 2 << ' ';
for (int i = 0; i < n; ++i) cout << ans[i] << " \n"[i == n - 1];
}
int main()
{
int t;
cin >> t;
while (t--) solve();
}