Add files using upload-large-folder tool

1fd0050 verified 6 months ago

6.1 kB

// Same as simulator.cpp but with more diagnostics
#include <bits/stdc++.h>
#include <unistd.h>
#include <sys/wait.h>
#include <signal.h>
using namespace std;

int main(int argc, char* argv[]) {
    int n = 100000, subtask = 3;
    if (argc > 1) n = atoi(argv[1]);
    if (argc > 2) subtask = atoi(argv[2]);

    vector<int> ring(n);
    iota(ring.begin(), ring.end(), 1);
    mt19937 rng(42);
    shuffle(ring.begin(), ring.end(), rng);

    vector<int> pos(n+1);
    for (int i = 0; i < n; i++) pos[ring[i]] = i;

    vector<int> vis(n+2, 0);
    int an = 0;

    auto flip2 = [&](int u) -> int {
        int pu = pos[u] + 1;
        if ((vis[pu] ^= 1)) {
            an += vis[pu-1] + vis[pu+1];
        } else {
            an -= vis[pu-1] + vis[pu+1];
        }
        return an || (vis[1] && vis[n]);
    };

    int pipe_to_sol[2], pipe_from_sol[2];
    pipe(pipe_to_sol);
    pipe(pipe_from_sol);

    pid_t pid = fork();
    if (pid == 0) {
        close(pipe_to_sol[1]);
        close(pipe_from_sol[0]);
        dup2(pipe_to_sol[0], STDIN_FILENO);
        dup2(pipe_from_sol[1], STDOUT_FILENO);
        close(pipe_to_sol[0]);
        close(pipe_from_sol[1]);
        execl("./solution_v2", "solution_v2", nullptr);
        perror("execl");
        _exit(1);
    }

    close(pipe_to_sol[0]);
    close(pipe_from_sol[1]);

    FILE* to_sol = fdopen(pipe_to_sol[1], "w");
    FILE* from_sol = fdopen(pipe_from_sol[0], "r");

    auto readIntFrom = [&]() -> int {
        int c = fgetc(from_sol);
        while (c != '-' && (c < '0' || c > '9')) {
            if (c == EOF) return -999;
            c = fgetc(from_sol);
        }
        int sgn = 1;
        if (c == '-') { sgn = -1; c = fgetc(from_sol); }
        int x = 0;
        while (c >= '0' && c <= '9') { x = x*10+(c-'0'); c = fgetc(from_sol); }
        return x * sgn;
    };

    int cnt_round = 0, cnt_query = 0;
    auto start_time = chrono::steady_clock::now();

    fprintf(to_sol, "%d %d\n", subtask, n);
    fflush(to_sol);

    bool correct = false;
    bool error = false;
    int max_round_size = 0;

    while (true) {
        int N = readIntFrom();
        if (N == -999) { fprintf(stderr, "EOF from solution\n"); error = true; break; }
        if (N == -1) {
            vector<int> ans(n);
            for (int i = 0; i < n; i++) {
                ans[i] = readIntFrom();
                if (ans[i] == -999) { error = true; break; }
            }
            if (error) break;

            int opt = -1;
            for (int i = 0; i < n; i++) if (ans[0] == ring[i]) { opt = i; break; }
            if (opt == -1) { fprintf(stderr, "Answer vertex not in ring\n"); break; }

            bool f1 = true, f2 = true;
            int mismatch_idx = -1;
            for (int i = 1; i < n; i++) {
                int op1 = (opt + i) % n;
                int op2 = (opt - i + n) % n;
                if (ring[op1] != ans[i]) f1 = false;
                if (ring[op2] != ans[i]) f2 = false;
                if (!f1 && !f2) { mismatch_idx = i; break; }
            }
            correct = f1 || f2;
            if (!correct) {
                fprintf(stderr, "Mismatch at index %d\n", mismatch_idx);
                fprintf(stderr, "ans[%d]=%d, expected fwd=%d or bwd=%d\n",
                    mismatch_idx, ans[mismatch_idx],
                    ring[(opt + mismatch_idx) % n],
                    ring[(opt - mismatch_idx + n) % n]);
                // Count how many answer vertices are valid ring vertices
                set<int> ansSet(ans.begin(), ans.end());
                fprintf(stderr, "Unique answer vertices: %d / %d\n", (int)ansSet.size(), n);
                // Check if answer is a valid permutation
                bool validPerm = (int)ansSet.size() == n;
                for (int v : ans) if (v < 1 || v > n) { validPerm = false; break; }
                fprintf(stderr, "Valid permutation: %s\n", validPerm ? "yes" : "no");
                // Check how many edges in answer match ring edges
                set<pair<int,int>> ringEdges;
                for (int i = 0; i < n; i++) {
                    int a = ring[i], b = ring[(i+1)%n];
                    ringEdges.insert({min(a,b), max(a,b)});
                }
                int matchEdges = 0;
                for (int i = 0; i < n; i++) {
                    int a = ans[i], b = ans[(i+1)%n];
                    if (ringEdges.count({min(a,b), max(a,b)})) matchEdges++;
                }
                fprintf(stderr, "Matching edges in answer: %d / %d\n", matchEdges, n);
            }
            break;
        }

        if (N > 10000000) {
            fprintf(stderr, "Round %d: SINGLE_QUERY_LIM exceeded: %d > 10M\n", cnt_round+1, N);
            // Still process it for testing
        }

        cnt_round++;
        cnt_query += N;
        if (N > max_round_size) max_round_size = N;

        vector<int> ops(N);
        for (int i = 0; i < N; i++) {
            ops[i] = readIntFrom();
            if (ops[i] == -999) { error = true; break; }
        }
        if (error) break;

        for (int i = 0; i < N; i++) {
            int res = flip2(ops[i]);
            if (i > 0) fputc(' ', to_sol);
            fprintf(to_sol, "%d", res);
        }
        fputc('\n', to_sol);
        fflush(to_sol);
    }

    auto end_time = chrono::steady_clock::now();
    double elapsed = chrono::duration<double>(end_time - start_time).count();

    fclose(to_sol);
    fclose(from_sol);

    int status;
    waitpid(pid, &status, 0);

    auto f = [](double x) -> double { return min(max(log2(x), 0.0), 8.0); };
    double lambda_val = max(0.0, 1.0 - 0.1 * (f(cnt_round / 18.0) + f(cnt_query / 1.5e7)));

    printf("=== Results ===\n");
    printf("Correct: %s\n", correct ? "YES" : "NO");
    printf("Rounds: %d\n", cnt_round);
    printf("Queries: %d\n", cnt_query);
    printf("Max round size: %d\n", max_round_size);
    printf("Time: %.3f s\n", elapsed);
    printf("Lambda: %.4f\n", lambda_val);
    printf("f(rounds): %.4f\n", f(cnt_round / 18.0));
    printf("f(queries): %.4f\n", f(cnt_query / 1.5e7));

    return correct ? 0 : 1;
}

	// Same as simulator.cpp but with more diagnostics
	#include <bits/stdc++.h>
	#include <unistd.h>
	#include <sys/wait.h>
	#include <signal.h>
	using namespace std;

	int main(int argc, char* argv[]) {
	int n = 100000, subtask = 3;
	if (argc > 1) n = atoi(argv[1]);
	if (argc > 2) subtask = atoi(argv[2]);

	vector<int> ring(n);
	iota(ring.begin(), ring.end(), 1);
	mt19937 rng(42);
	shuffle(ring.begin(), ring.end(), rng);

	vector<int> pos(n+1);
	for (int i = 0; i < n; i++) pos[ring[i]] = i;

	vector<int> vis(n+2, 0);
	int an = 0;

	auto flip2 = [&](int u) -> int {
	int pu = pos[u] + 1;
	if ((vis[pu] ^= 1)) {
	an += vis[pu-1] + vis[pu+1];
	} else {
	an -= vis[pu-1] + vis[pu+1];
	}
	return an \|\| (vis[1] && vis[n]);
	};

	int pipe_to_sol[2], pipe_from_sol[2];
	pipe(pipe_to_sol);
	pipe(pipe_from_sol);

	pid_t pid = fork();
	if (pid == 0) {
	close(pipe_to_sol[1]);
	close(pipe_from_sol[0]);
	dup2(pipe_to_sol[0], STDIN_FILENO);
	dup2(pipe_from_sol[1], STDOUT_FILENO);
	close(pipe_to_sol[0]);
	close(pipe_from_sol[1]);
	execl("./solution_v2", "solution_v2", nullptr);
	perror("execl");
	_exit(1);
	}

	close(pipe_to_sol[0]);
	close(pipe_from_sol[1]);

	FILE* to_sol = fdopen(pipe_to_sol[1], "w");
	FILE* from_sol = fdopen(pipe_from_sol[0], "r");

	auto readIntFrom = [&]() -> int {
	int c = fgetc(from_sol);
	while (c != '-' && (c < '0' \|\| c > '9')) {
	if (c == EOF) return -999;
	c = fgetc(from_sol);
	}
	int sgn = 1;
	if (c == '-') { sgn = -1; c = fgetc(from_sol); }
	int x = 0;
	while (c >= '0' && c <= '9') { x = x*10+(c-'0'); c = fgetc(from_sol); }
	return x * sgn;
	};

	int cnt_round = 0, cnt_query = 0;
	auto start_time = chrono::steady_clock::now();

	fprintf(to_sol, "%d %d\n", subtask, n);
	fflush(to_sol);

	bool correct = false;
	bool error = false;
	int max_round_size = 0;

	while (true) {
	int N = readIntFrom();
	if (N == -999) { fprintf(stderr, "EOF from solution\n"); error = true; break; }
	if (N == -1) {
	vector<int> ans(n);
	for (int i = 0; i < n; i++) {
	ans[i] = readIntFrom();
	if (ans[i] == -999) { error = true; break; }
	}
	if (error) break;

	int opt = -1;
	for (int i = 0; i < n; i++) if (ans[0] == ring[i]) { opt = i; break; }
	if (opt == -1) { fprintf(stderr, "Answer vertex not in ring\n"); break; }

	bool f1 = true, f2 = true;
	int mismatch_idx = -1;
	for (int i = 1; i < n; i++) {
	int op1 = (opt + i) % n;
	int op2 = (opt - i + n) % n;
	if (ring[op1] != ans[i]) f1 = false;
	if (ring[op2] != ans[i]) f2 = false;
	if (!f1 && !f2) { mismatch_idx = i; break; }
	}
	correct = f1 \|\| f2;
	if (!correct) {
	fprintf(stderr, "Mismatch at index %d\n", mismatch_idx);
	fprintf(stderr, "ans[%d]=%d, expected fwd=%d or bwd=%d\n",
	mismatch_idx, ans[mismatch_idx],
	ring[(opt + mismatch_idx) % n],
	ring[(opt - mismatch_idx + n) % n]);
	// Count how many answer vertices are valid ring vertices
	set<int> ansSet(ans.begin(), ans.end());
	fprintf(stderr, "Unique answer vertices: %d / %d\n", (int)ansSet.size(), n);
	// Check if answer is a valid permutation
	bool validPerm = (int)ansSet.size() == n;
	for (int v : ans) if (v < 1 \|\| v > n) { validPerm = false; break; }
	fprintf(stderr, "Valid permutation: %s\n", validPerm ? "yes" : "no");
	// Check how many edges in answer match ring edges
	set<pair<int,int>> ringEdges;
	for (int i = 0; i < n; i++) {
	int a = ring[i], b = ring[(i+1)%n];
	ringEdges.insert({min(a,b), max(a,b)});
	}
	int matchEdges = 0;
	for (int i = 0; i < n; i++) {
	int a = ans[i], b = ans[(i+1)%n];
	if (ringEdges.count({min(a,b), max(a,b)})) matchEdges++;
	}
	fprintf(stderr, "Matching edges in answer: %d / %d\n", matchEdges, n);
	}
	break;
	}

	if (N > 10000000) {
	fprintf(stderr, "Round %d: SINGLE_QUERY_LIM exceeded: %d > 10M\n", cnt_round+1, N);
	// Still process it for testing
	}

	cnt_round++;
	cnt_query += N;
	if (N > max_round_size) max_round_size = N;

	vector<int> ops(N);
	for (int i = 0; i < N; i++) {
	ops[i] = readIntFrom();
	if (ops[i] == -999) { error = true; break; }
	}
	if (error) break;

	for (int i = 0; i < N; i++) {
	int res = flip2(ops[i]);
	if (i > 0) fputc(' ', to_sol);
	fprintf(to_sol, "%d", res);
	}
	fputc('\n', to_sol);
	fflush(to_sol);
	}

	auto end_time = chrono::steady_clock::now();
	double elapsed = chrono::duration<double>(end_time - start_time).count();

	fclose(to_sol);
	fclose(from_sol);

	int status;
	waitpid(pid, &status, 0);

	auto f = [](double x) -> double { return min(max(log2(x), 0.0), 8.0); };
	double lambda_val = max(0.0, 1.0 - 0.1 * (f(cnt_round / 18.0) + f(cnt_query / 1.5e7)));

	printf("=== Results ===\n");
	printf("Correct: %s\n", correct ? "YES" : "NO");
	printf("Rounds: %d\n", cnt_round);
	printf("Queries: %d\n", cnt_query);
	printf("Max round size: %d\n", max_round_size);
	printf("Time: %.3f s\n", elapsed);
	printf("Lambda: %.4f\n", lambda_val);
	printf("f(rounds): %.4f\n", f(cnt_round / 18.0));
	printf("f(queries): %.4f\n", f(cnt_query / 1.5e7));

	return correct ? 0 : 1;
	}