Add files using upload-large-folder tool

1fd0050 verified 6 months ago

7.47 kB

// Standalone simulator: combines interactor logic + runs solution via pipes
// Usage: ./simulator <n> [subtask]
// Generates random ring, runs solution, reports results

#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]);

    // Generate random permutation
    vector<int> perm(n);
    iota(perm.begin(), perm.end(), 0);
    mt19937 rng(42);
    shuffle(perm.begin(), perm.end(), rng);

    // q[v] = position of vertex v in the ring (1-indexed)
    vector<int> q(n+1);
    for (int i = 0; i < n; i++) q[perm[i]+1] = i+1; // wait, perm is 0-indexed
    // Actually: perm[i] is the i-th vertex label (0-indexed). Let me redo.
    // The ring is: perm[0] - perm[1] - ... - perm[n-1] - perm[0]
    // p[i] = perm[i] (the ring order, 0-indexed)
    // q[perm[i]] = i (position in ring, 0-indexed)
    // But interactor uses 1-indexed: p[i] for i=0..n-1, q[p[i]] = i+1

    // Let's use the interactor's convention
    vector<int> p(n), qq(n+1);
    for (int i = 0; i < n; i++) p[i] = perm[i]; // ring order (0-indexed values)
    for (int i = 0; i < n; i++) qq[p[i]] = i+1; // 1-indexed position
    // Wait, interactor: q[p[i]] = i+1, where p[i] is read from answer file
    // But in interactor, vertices are 1..n
    // Let me re-generate with 1-indexed vertices

    vector<int> ring(n);
    iota(ring.begin(), ring.end(), 1); // 1..n
    shuffle(ring.begin(), ring.end(), rng);
    // ring[0]-ring[1]-...-ring[n-1]-ring[0]

    // q[ring[i]] = i+1 (1-indexed position in ring)
    // So ring[i] is at position i+1
    // Two vertices are adjacent iff their positions differ by 1 (mod n)

    vector<int> pos(n+1); // pos[v] = 0-indexed position in ring
    for (int i = 0; i < n; i++) pos[ring[i]] = i;

    // Interactor state
    vector<int> vis(n+2, 0); // vis[position], 1-indexed positions, with sentinel
    int an = 0; // adjacency count

    auto flip = [&](int u) -> int {
        int pu = pos[u] + 1; // 1-indexed position
        if ((vis[pu] ^= 1)) {
            an += vis[pu == 1 ? n : pu-1] + vis[pu == n ? 1 : pu+1];
        } else {
            an -= vis[pu == 1 ? n : pu-1] + vis[pu == n ? 1 : pu+1];
        }
        return an > 0 || (vis[1] && vis[n]);
        // Wait, the original uses: return an || (vis[1] && vis[n])
        // where vis uses positions 1..n and checks vis[u-1] and vis[u+1]
        // But positions 1 and n are adjacent in the ring!
        // In the original: q[u] gives position 1..n
        // vis[q[u]-1] and vis[q[u]+1] are checked
        // vis[0] and vis[n+1] are always 0 (sentinel)
        // But wait - vertices at positions 1 and n are adjacent!
        // The formula an += vis[u-1] + vis[u+1] misses the wrap-around
        // That's why there's the special case: return an || (vis[1] && vis[n])
    };

    // Actually let me just faithfully replicate the interactor logic
    // Reset
    an = 0;
    fill(vis.begin(), vis.end(), 0);
    vis.resize(n+2, 0); // positions 0..n+1, with 0 and n+1 as sentinels

    auto flip2 = [&](int u) -> int {
        int pu = pos[u] + 1; // 1-indexed
        if ((vis[pu] ^= 1)) {
            // Check neighbors in the linear array (not circular)
            an += vis[pu-1] + vis[pu+1];
        } else {
            an -= vis[pu-1] + vis[pu+1];
        }
        // Return 1 if any adjacency exists, OR if both endpoints of the ring are active
        return an || (vis[1] && vis[n]);
    };

    // Create pipes
    int pipe_to_sol[2], pipe_from_sol[2];
    pipe(pipe_to_sol);   // interactor writes, solution reads
    pipe(pipe_from_sol); // solution writes, interactor reads

    pid_t pid = fork();
    if (pid == 0) {
        // Child: solution
        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_bin", "solution_bin", nullptr);
        perror("execl");
        _exit(1);
    }

    // Parent: interactor
    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;
    };

    auto writeIntTo = [&](int x) {
        fprintf(to_sol, "%d", x);
    };

    int cnt_round = 0, cnt_query = 0;

    auto start_time = chrono::steady_clock::now();

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

    bool correct = false;
    bool error = false;

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

            // Check answer
            // Find ring[0] in ans
            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;
            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) break;
            }
            correct = f1 || f2;
            break;
        }

        cnt_round++;
        cnt_query += N;

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

        // Process and send results
        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);

    // Compute score
    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("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;
}

	// Standalone simulator: combines interactor logic + runs solution via pipes
	// Usage: ./simulator <n> [subtask]
	// Generates random ring, runs solution, reports results

	#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]);

	// Generate random permutation
	vector<int> perm(n);
	iota(perm.begin(), perm.end(), 0);
	mt19937 rng(42);
	shuffle(perm.begin(), perm.end(), rng);

	// q[v] = position of vertex v in the ring (1-indexed)
	vector<int> q(n+1);
	for (int i = 0; i < n; i++) q[perm[i]+1] = i+1; // wait, perm is 0-indexed
	// Actually: perm[i] is the i-th vertex label (0-indexed). Let me redo.
	// The ring is: perm[0] - perm[1] - ... - perm[n-1] - perm[0]
	// p[i] = perm[i] (the ring order, 0-indexed)
	// q[perm[i]] = i (position in ring, 0-indexed)
	// But interactor uses 1-indexed: p[i] for i=0..n-1, q[p[i]] = i+1

	// Let's use the interactor's convention
	vector<int> p(n), qq(n+1);
	for (int i = 0; i < n; i++) p[i] = perm[i]; // ring order (0-indexed values)
	for (int i = 0; i < n; i++) qq[p[i]] = i+1; // 1-indexed position
	// Wait, interactor: q[p[i]] = i+1, where p[i] is read from answer file
	// But in interactor, vertices are 1..n
	// Let me re-generate with 1-indexed vertices

	vector<int> ring(n);
	iota(ring.begin(), ring.end(), 1); // 1..n
	shuffle(ring.begin(), ring.end(), rng);
	// ring[0]-ring[1]-...-ring[n-1]-ring[0]

	// q[ring[i]] = i+1 (1-indexed position in ring)
	// So ring[i] is at position i+1
	// Two vertices are adjacent iff their positions differ by 1 (mod n)

	vector<int> pos(n+1); // pos[v] = 0-indexed position in ring
	for (int i = 0; i < n; i++) pos[ring[i]] = i;

	// Interactor state
	vector<int> vis(n+2, 0); // vis[position], 1-indexed positions, with sentinel
	int an = 0; // adjacency count

	auto flip = [&](int u) -> int {
	int pu = pos[u] + 1; // 1-indexed position
	if ((vis[pu] ^= 1)) {
	an += vis[pu == 1 ? n : pu-1] + vis[pu == n ? 1 : pu+1];
	} else {
	an -= vis[pu == 1 ? n : pu-1] + vis[pu == n ? 1 : pu+1];
	}
	return an > 0 \|\| (vis[1] && vis[n]);
	// Wait, the original uses: return an \|\| (vis[1] && vis[n])
	// where vis uses positions 1..n and checks vis[u-1] and vis[u+1]
	// But positions 1 and n are adjacent in the ring!
	// In the original: q[u] gives position 1..n
	// vis[q[u]-1] and vis[q[u]+1] are checked
	// vis[0] and vis[n+1] are always 0 (sentinel)
	// But wait - vertices at positions 1 and n are adjacent!
	// The formula an += vis[u-1] + vis[u+1] misses the wrap-around
	// That's why there's the special case: return an \|\| (vis[1] && vis[n])
	};

	// Actually let me just faithfully replicate the interactor logic
	// Reset
	an = 0;
	fill(vis.begin(), vis.end(), 0);
	vis.resize(n+2, 0); // positions 0..n+1, with 0 and n+1 as sentinels

	auto flip2 = [&](int u) -> int {
	int pu = pos[u] + 1; // 1-indexed
	if ((vis[pu] ^= 1)) {
	// Check neighbors in the linear array (not circular)
	an += vis[pu-1] + vis[pu+1];
	} else {
	an -= vis[pu-1] + vis[pu+1];
	}
	// Return 1 if any adjacency exists, OR if both endpoints of the ring are active
	return an \|\| (vis[1] && vis[n]);
	};

	// Create pipes
	int pipe_to_sol[2], pipe_from_sol[2];
	pipe(pipe_to_sol); // interactor writes, solution reads
	pipe(pipe_from_sol); // solution writes, interactor reads

	pid_t pid = fork();
	if (pid == 0) {
	// Child: solution
	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_bin", "solution_bin", nullptr);
	perror("execl");
	_exit(1);
	}

	// Parent: interactor
	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;
	};

	auto writeIntTo = [&](int x) {
	fprintf(to_sol, "%d", x);
	};

	int cnt_round = 0, cnt_query = 0;

	auto start_time = chrono::steady_clock::now();

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

	bool correct = false;
	bool error = false;

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

	// Check answer
	// Find ring[0] in ans
	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;
	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) break;
	}
	correct = f1 \|\| f2;
	break;
	}

	cnt_round++;
	cnt_query += N;

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

	// Process and send results
	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);

	// Compute score
	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("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;
	}