Submission #1251767

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251767		coin_	Permutation Game (APIO25_permgame)	C++20	0 / 100	1 ms	328 KiB

permgame

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

// Forward declaration of the grader's function for interaction with Bob.
int Bob(std::vector<int> t);

namespace {
    // Helper structures for graph analysis and permutation tracking.
    std::vector<std::vector<int>> adj;
    std::vector<int> color;
    std::vector<bool> visited;

    // Utility function to check for bipartiteness using 2-coloring (BFS/DFS).
    // It's run on the graph which is known to be connected.
    bool is_bipartite_util(int u, int c) {
        visited[u] = true;
        color[u] = c;
        for (int v : adj[u]) {
            if (!visited[v]) {
                if (!is_bipartite_util(v, 1 - c)) {
                    return false;
                }
            } else if (color[v] == color[u]) {
                return false;
            }
        }
        return true;
    }
}

int Alice(int m, int e, std::vector<int> u, std::vector<int> v,
          int n, std::vector<int> p) {
    
    // 1. Calculate the initial score of the permutation.
    int initial_score = 0;
    for (int i = 0; i < n; ++i) {
        if (p[i] == i) {
            initial_score++;
        }
    }

    // 2. Analyze the graph's structure.
    adj.assign(m, std::vector<int>());
    for (int i = 0; i < e; ++i) {
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    }

    visited.assign(m, false);
    color.assign(m, -1);
    // The problem statement guarantees the graph is connected.
    bool is_graph_bipartite = is_bipartite_util(0, 0);

    // If the graph is bipartite, Alice cannot guarantee forcing the swaps she needs.
    // No improvement is possible against an optimal Bob.
    if (is_graph_bipartite) {
        return initial_score;
    }

    // 3. If non-bipartite, find winnable permutation cycles.
    // A cycle C is winnable if |C| >= 2m - 1. This ensures Alice can always
    // continue breaking it down until a fixed point is made.
    long long required_cycle_size = 2LL * m - 1;
    int winnable_cycles_count = 0;
    std::vector<std::vector<int>> winnable_cycles_nodes;

    visited.assign(n, false);
    for (int i = 0; i < n; ++i) {
        if (p[i] == i || visited[i]) {
            continue;
        }
        
        std::vector<int> current_cycle;
        int current = i;
        while (!visited[current]) {
            visited[current] = true;
            current_cycle.push_back(current);
            current = p[current];
        }
        
        if (current_cycle.size() >= required_cycle_size) {
            winnable_cycles_count++;
            winnable_cycles_nodes.push_back(current_cycle);
        }
    }

    int optimal_score = initial_score + winnable_cycles_count;

    // 4. Play the game to achieve the optimal score, if it's higher than the start.
    if (optimal_score > initial_score) {
        for (const auto& cycle_to_fix : winnable_cycles_nodes) {
            int target_node = cycle_to_fix[0];
            std::vector<int> current_piece = cycle_to_fix;

            // Keep playing on this cycle until our target becomes a fixed point.
            while (p[target_node] != target_node) {
                std::vector<int> t(m);
                // Map the first m nodes of the current cycle piece to the graph vertices.
                // The size condition guarantees the piece is large enough to do this
                // until the very end.
                for (int k = 0; k < m; ++k) {
                    t[k] = current_piece[k];
                }

                int edge_j = Bob(t);
                std::swap(p[t[u[edge_j]]], p[t[v[edge_j]]]);

                // After the swap, re-evaluate the cycle piece containing our target node.
                std::vector<bool> visited_piece(n, false);
                current_piece.clear();
                int current = target_node;
                while (!visited_piece[current] && p[current] != current) {
                    visited_piece[current] = true;
                    current_piece.push_back(current);
                    current = p[current];
                }
            }
        }
    }

    return optimal_score;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 6
• Subtask 2: 0 / 6
• Subtask 3: 0 / 10
• Subtask 4: 0 / 24
• Subtask 5: 0 / 24
• Subtask 6: 0 / 30