結果

問題 No.3400 Nana's Plus Permutation Game (7 + 7) ÷ 7
コンテスト
ユーザー Mike scarf
提出日時 2025-12-12 16:58:09
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
RE  
実行時間 -
コード長 4,193 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,151 ms
コンパイル使用メモリ 288,928 KB
実行使用メモリ 26,692 KB
平均クエリ数 10513.68
最終ジャッジ日時 2025-12-12 16:58:58
合計ジャッジ時間 44,663 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 1 RE * 76
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

/*************************************************
 *  Interactive solver for the “P_i + P_j = P_k” game
 *  -------------------------------------------------
 *  protocol
 *      • judge sends:      T
 *      • loop T times
 *            judge sends:  N        (prime, 5 ≤ N)
 *            we may send up to 3N queries
 *                  1 i j            (1 ≤ i,j ≤ N, i≠j)
 *                  flush
 *                  judge answers:   k  (1..N) or -1
 *            finally
 *                  2 P1 P2 ... PN
 *                  flush
 *************************************************/
#include <bits/stdc++.h>
using namespace std;

static constexpr long long INF64 = (1LL << 60);

/* ---------- small helper ------------- */
void flush_out() {
    cout << std::flush;
}
int ask(int i, int j) {          // send query and read reply
    cout << "1 " << i << ' ' << j << '\n';
    flush_out();
    int k;
    if (!(cin >> k)) exit(0);    // judge terminated
    return k;
}
void answer(const vector<int>& P) {
    cout << "2";
    for (int x : P) cout << ' ' << x;
    cout << '\n';
    flush_out();
}

/* ---------- main logic per test case ----------- */
struct Equation { int a, b, c; };        // Pa + Pb = Pc
void solve_case(int N)
{
    int r = 1, s = 2;                    // two star centres
    vector<Equation> eqs; eqs.reserve(2*N);

    /* ---- first star centred at r ---- */
    for (int i = 1; i <= N; ++i)
        if (i != r) {
            int k = ask(r, i);
            if (k != -1) eqs.push_back({r, i, k});
        }

    /* ---- second star centred at s ---- */
    for (int i = 1; i <= N; ++i)
        if (i != s) {
            int k = ask(s, i);
            if (k != -1) eqs.push_back({s, i, k});
        }

    /* ---- propagate α so that  P_i = μ + α_i · λ ---- */
    vector<long long> alpha(N + 1, INF64);   // 1-based
    alpha[r] = 0;
    alpha[s] = 1;
    bool updated = true;
    while (updated) {
        updated = false;
        for (const auto& e : eqs) {
            long long A = alpha[e.a], B = alpha[e.b], C = alpha[e.c];
            if (A != INF64 && B != INF64 && C == INF64) {
                alpha[e.c] = A + B; updated = true;
            } else if (A != INF64 && C != INF64 && B == INF64) {
                alpha[e.b] = C - A; updated = true;
            } else if (B != INF64 && C != INF64 && A == INF64) {
                alpha[e.a] = C - B; updated = true;
            }
        }
    }
    /* 所有点都应已确定 */
    for (int i = 1; i <= N; ++i)
        if (alpha[i] == INF64) {
            cerr << "alpha unresolved at " << i << endl;
            exit(1);
        }

    long long amin = *min_element(alpha.begin() + 1, alpha.end());
    long long amax = *max_element(alpha.begin() + 1, alpha.end());

    long long denom = amax - amin;        // >0
    long long numer = N - 1;

    /* λ 只可能是  ± numer/denom  */
    if (numer % denom != 0) {
        cerr << "lambda not integral???\n";
        exit(1);
    }
    long long lam_abs = numer / denom;

    auto try_build = [&](long long lam) -> optional<vector<int>> {
        long long mu = 1 - amin * lam;            // 使最小值映射到 1
        vector<int> P(N + 1);
        vector<char> seen(N + 1, 0);
        for (int i = 1; i <= N; ++i) {
            long long val = mu + alpha[i] * lam;
            if (val < 1 || val > N) return {};    // out of range
            P[i] = (int)val;
            if (seen[P[i]]) return {};            // duplicate
            seen[P[i]] = 1;
        }
        return P;
    };

    auto cand = try_build( lam_abs );
    if (!cand) cand = try_build( -lam_abs );      // opposite direction

    if (!cand) {
        cerr << "No consistent permutation found\n";
        exit(1);
    }

    answer(*cand);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    if (!(cin >> T)) return 0;
    while (T--) {
        int N; cin >> N;
        solve_case(N);
        /* judge may respond something; ignore */
        int verdict;
        if (!(cin >> verdict)) break;     // finished normally
        if (verdict != 1) break;          // 1 = OK (typical); else stop
    }
    return 0;
}
0