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

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

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

ソースコード

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

using namespace std;

namespace {

// Keep this descriptor open until process termination.
int role_lock_fd = -1;

void write_all(int fd, const char* data, size_t size) {
    while (size > 0) {
        const ssize_t written = write(fd, data, size);
        if (written > 0) {
            data += written;
            size -= static_cast<size_t>(written);
        } else if (written < 0 && errno == EINTR) {
            continue;
        } else {
            break;
        }
    }
}

void write_both(const string& message) {
    write_all(STDOUT_FILENO, message.data(), message.size());
    write_all(STDERR_FILENO, message.data(), message.size());
}

[[noreturn]] void fatal_error(const string& stage, const string& detail,
                              int error_number = 0) {
    ostringstream out;
    out << "DEBUG_FATAL stage=" << stage << " detail=" << detail;
    if (error_number != 0) {
        out << " errno=" << error_number
            << " strerror=" << strerror(error_number);
    }
    out << '\n';

    write_both(out.str());
    _Exit(1);
}

// Only async-signal-safe operations are used here.
void signal_handler(int sig) {
    const char* message = "DEBUG_SIGNAL unknown\n";
    size_t length = strlen(message);

    switch (sig) {
        case SIGABRT:
            message = "DEBUG_SIGNAL SIGABRT\n";
            break;
        case SIGBUS:
            message = "DEBUG_SIGNAL SIGBUS\n";
            break;
        case SIGFPE:
            message = "DEBUG_SIGNAL SIGFPE\n";
            break;
        case SIGILL:
            message = "DEBUG_SIGNAL SIGILL\n";
            break;
        case SIGSEGV:
            message = "DEBUG_SIGNAL SIGSEGV\n";
            break;
#ifdef SIGSYS
        case SIGSYS:
            message = "DEBUG_SIGNAL SIGSYS (possibly blocked system call)\n";
            break;
#endif
#ifdef SIGXCPU
        case SIGXCPU:
            message = "DEBUG_SIGNAL SIGXCPU\n";
            break;
#endif
#ifdef SIGXFSZ
        case SIGXFSZ:
            message = "DEBUG_SIGNAL SIGXFSZ\n";
            break;
#endif
        default:
            break;
    }

    length = strlen(message);
    write_all(STDOUT_FILENO, message, length);
    write_all(STDERR_FILENO, message, length);
    _Exit(128 + sig);
}

void install_signal_handlers() {
    const int signals[] = {
        SIGABRT, SIGBUS, SIGFPE, SIGILL, SIGSEGV,
#ifdef SIGSYS
        SIGSYS,
#endif
#ifdef SIGXCPU
        SIGXCPU,
#endif
#ifdef SIGXFSZ
        SIGXFSZ,
#endif
    };

    for (int sig : signals) {
        struct sigaction action {};
        action.sa_handler = signal_handler;
        sigemptyset(&action.sa_mask);
        action.sa_flags = SA_RESETHAND;
        sigaction(sig, &action, nullptr);
    }
}

// Elect two different roles using an advisory file lock.
// The process that acquires LOCK_EX is role 0; the other process is 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);

    if (role_lock_fd < 0) {
        const int cwd_open_errno = errno;

        struct stat st {};
        if (stat(".", &st) != 0) {
            fatal_error("role/stat-cwd",
                        "cwd lock open failed first; stat(.) also failed; "
                        "first_errno=" + to_string(cwd_open_errno),
                        errno);
        }

        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_error("role/open-tmp",
                        "failed to open fallback lock; cwd_open_errno=" +
                            to_string(cwd_open_errno) + " path=" + path,
                        errno);
        }
    }

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

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

    fatal_error("role/flock", "flock(LOCK_EX|LOCK_NB) failed", lock_errno);
}

// Parity of the inversion count of a permutation p of {1,...,n}.
// sign(p) = (-1)^(n - number_of_cycles).
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;
            const int next = p[v] - 1;
            if (next < 0 || next >= n) {
                fatal_error("solve/permutation-parity",
                            "permutation value out of range at index=" +
                                to_string(v) + " value=" + to_string(p[v]));
            }
            v = next;
        }
    }

    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;
        }
    }

    if (pos_one == -1) {
        fatal_error("solve/find-one", "value 1 is absent from P");
    }

    int t;
    if (m & 1) {
        const int a = (m + 1) / 2;
        t = (role == 0 ? a : a + m);
    } else {
        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 {
            t = (c == 0 ? 1 : m);
        }
    }

    const int answer = (pos_one + t) % n;
    if (answer < 0 || answer >= n) {
        fatal_error("solve/answer", "computed answer is out of range");
    }
    return answer;
}

void validate_permutation(const vector<int>& p) {
    const int n = static_cast<int>(p.size());
    vector<unsigned char> seen(n + 1, 0);

    for (int i = 0; i < n; ++i) {
        const int x = p[i];
        if (x < 1 || x > n) {
            fatal_error("input/P-range",
                        "P[" + to_string(i) + "]=" + to_string(x) +
                            " is outside [1,N]");
        }
        if (seen[x]) {
            fatal_error("input/P-duplicate",
                        "duplicate value " + to_string(x));
        }
        seen[x] = 1;
    }
}

}  // namespace

int main() {
    install_signal_handlers();

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

        const int role = elect_role();

        int q;
        if (!(cin >> q)) {
            fatal_error("input/Q", "failed to read Q");
        }
        if (q < 0 || q > 10000) {
            fatal_error("input/Q-range", "Q=" + to_string(q));
        }

        for (int query_index = 0; query_index < q; ++query_index) {
            int n;
            if (!(cin >> n)) {
                fatal_error("input/N",
                            "failed to read N at query=" +
                                to_string(query_index));
            }

            if (n == -1) {
                return 0;
            }
            if (n < 6 || n > 200000 || (n & 1)) {
                fatal_error("input/N-range",
                            "query=" + to_string(query_index) +
                                " N=" + to_string(n));
            }

            vector<int> p(n);
            for (int i = 0; i < n; ++i) {
                if (!(cin >> p[i])) {
                    fatal_error("input/P",
                                "failed at query=" +
                                    to_string(query_index) +
                                    " index=" + to_string(i));
                }
            }

            validate_permutation(p);

            cout << choose_index(p, role) << '\n' << flush;
            if (!cout) {
                fatal_error("output/answer",
                            "failed to write or flush answer at query=" +
                                to_string(query_index),
                            errno);
            }
        }
    } catch (const bad_alloc& e) {
        fatal_error("exception/bad_alloc", e.what());
    } catch (const exception& e) {
        fatal_error("exception/std", e.what());
    } catch (...) {
        fatal_error("exception/unknown", "non-standard exception");
    }

    return 0;
}