제출 #1251773

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1251773		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).
    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 (is_graph_bipartite) {
        return initial_score;
    }

    // 3. If non-bipartite, find winnable permutation cycles.
    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 (optimal_score > initial_score) {
        for (const auto& cycle_to_fix : winnable_cycles_nodes) {
            int target_node = cycle_to_fix[0];
            
            // This vector will hold the nodes of the cycle piece we are currently working on.
            std::vector<int> current_piece_nodes = cycle_to_fix;

            while (p[target_node] != target_node) {
                // The condition k >= 2m-1 guarantees that the piece containing the
                // target node will have a size of at least m, until it is fully resolved.
                std::vector<int> t(m);
                for (int k = 0; k < m; ++k) {
                    t[k] = current_piece_nodes[k];
                }

                int edge_j = Bob(t);
                
                // Find which permutation indices correspond to the swapped edge
                int p_idx1 = -1, p_idx2 = -1;
                for(int k=0; k<m; ++k){
                    if(t[k] == u[edge_j] || t[k] == v[edge_j]){
                         bool mapping_found = false;
                         for(int l=0; l<m; ++l){
                            if(u[edge_j] == l && t[l] == t[k]) mapping_found = true;
                            if(v[edge_j] == l && t[l] == t[k]) mapping_found = true;
                         }
                    }
                }
                
                // We need to find which t[k] were mapped to the vertices u[j] and v[j]
                // This requires reversing the implicit mapping.
                // A simpler way is to just find the values in t that correspond to the vertices.
                int t_for_u = -1, t_for_v = -1;
                // This is a simplification; the t vector index is the vertex number.
                t_for_u = t[u[edge_j]];
                t_for_v = t[v[edge_j]];

                std::swap(p[t_for_u], p[t_for_v]);

                // After Bob's swap, re-evaluate the cycle piece containing our target node.
                std::vector<bool> visited_piece(n, false);
                current_piece_nodes.clear();
                int current = target_node;
                // We trace the new cycle path starting from our target node.
                while (!visited_piece[current] && p[current] != current) {
                    visited_piece[current] = true;
                    current_piece_nodes.push_back(current);
                    current = p[current];
                }
                 if(p[current] == current && !visited_piece[current]){
                    visited_piece[current] = true;
                    current_piece_nodes.push_back(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