#1173890 (C++23) No.3783 Choose Disjoint Semicircles

• 問題: No.3783 Choose Disjoint Semicircles
• ユーザー: askr58
• 提出日時: 2026-07-27 22:02:48
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: RE
• 実行時間: -
• コード長: 3,632 bytes
• コンパイル時間: 2,829 ms
• コンパイル使用メモリ: 347,064 KB
• 実行使用メモリ: 9,812 KB
• 平均クエリ数: 1.00
• 最終ジャッジ日時: 2026-10-30 20:54:04
• 合計ジャッジ時間: 7,166 ms
• ジャッジサーバーID （参考情報）: judge7_0 / judge2_0

ファイルパターン	結果
sample	RE * 1
other	RE * 36

ソースコード

//generated by ChatGPT
#include <bits/stdc++.h>
#include <cerrno>
#include <fcntl.h>
#include <sys/file.h>
#include <sys/stat.h>
#include <unistd.h>

using namespace std;

namespace {

// プログラム終了まで開いたままにする。
int role_lock_fd = -1;

[[noreturn]] void fatal_lock_error(const string& message) {
    cerr << message
         << " (errno=" << errno << ": " << strerror(errno) << ")\n";
    exit(1);
}

// 排他ロックを取れたプロセスを role 0、
// 既に他方がロックしていたプロセスを role 1 とする。
int elect_role() {
    string path = ".yukicoder_half_reverse_role.lock";

    role_lock_fd =
        open(path.c_str(), O_CREAT | O_RDWR | O_CLOEXEC, 0600);

    // カレントディレクトリが書き込み不可の場合のフォールバック。
    // 両プロセスの cwd が同じなら同じパスになる。
    if (role_lock_fd < 0) {
        struct stat st{};
        if (stat(".", &st) != 0) {
            fatal_lock_error("failed to stat current directory");
        }

        path =
            "/tmp/yukicoder_half_reverse_role_" +
            to_string(
                static_cast<unsigned long long>(st.st_dev)
            ) +
            "_" +
            to_string(
                static_cast<unsigned long long>(st.st_ino)
            ) +
            ".lock";

        role_lock_fd =
            open(path.c_str(), O_CREAT | O_RDWR | O_CLOEXEC, 0600);

        if (role_lock_fd < 0) {
            fatal_lock_error("failed to open role lock file");
        }
    }

    if (flock(role_lock_fd, LOCK_EX | LOCK_NB) == 0) {
        return 0;
    }

    if (errno == EWOULDBLOCK || errno == EAGAIN) {
        return 1;
    }

    fatal_lock_error("flock is unavailable");
}

// Pの転倒数の偶奇。
// 順列の符号は (-1)^(N - 巡回置換の個数) で求められる。
int permutation_parity(const vector<int>& p) {
    const int n = static_cast<int>(p.size());

    vector<unsigned char> visited(n, 0);
    int cycles = 0;

    for (int start = 0; start < n; ++start) {
        if (visited[start]) continue;

        ++cycles;
        int v = start;

        while (!visited[v]) {
            visited[v] = 1;
            v = p[v] - 1;
        }
    }

    return (n - cycles) & 1;
}

int choose_index(const vector<int>& p, int role) {
    const int n = static_cast<int>(p.size());
    const int m = n / 2;

    int pos_one = -1;
    for (int i = 0; i < n; ++i) {
        if (p[i] == 1) {
            pos_one = i;
            break;
        }
    }

    // 出力位置を pos_one + t (mod N) と表す。
    int t;

    if (m & 1) {
        const int a = (m + 1) / 2;

        if (role == 0) {
            t = a;
        } else {
            t = a + m;
        }
    } else {
        // Nが偶数なので、巡回シフトに対して不変。
        const int c =
            permutation_parity(p) ^ (pos_one & 1);

        if (role == 0) {
            t = (c == 0 ? 0 : m + 1);
        } else if (m % 4 == 0) {
            t = (c == 0 ? m : 1);
        } else {
            // m % 4 == 2
            t = (c == 0 ? 1 : m);
        }
    }

    return (pos_one + t) % n;
}

} // namespace

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

    const int role = elect_role();

    int q;
    if (!(cin >> q)) return 0;

    while (q--) {
        int n;
        if (!(cin >> n)) return 0;

        if (n == -1) {
            return 0;
        }

        vector<int> p(n);
        for (int& x : p) {
            cin >> x;
        }

        cout << choose_index(p, role) << '\n' << flush;
    }

    return 0;
}