제출 #1288735

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288735		ecen30	세계 지도 (IOI25_worldmap)	C++20	0 / 100	3 ms	828 KiB

worldmap

//testing Ai code
#include "worldmap.h"
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
    // Build adjacency list
    vector<set<int>> adj(N + 1);
    for (int i = 0; i < M; i++) {
        adj[A[i]].insert(B[i]);
        adj[B[i]].insert(A[i]);
    }
    
    // Special case: No edges - just place all countries in a line
    if (M == 0) {
        vector<vector<int>> C(1, vector<int>(N));
        for (int i = 0; i < N; i++) {
            C[0][i] = i + 1;
        }
        return C;
    }
    
    // General strategy: Create a cross pattern for each country
    // Each country occupies a + shape, allowing edges in 4 directions
    // Grid size: 3N x 3N (each country gets a 3x3 region, uses center + 4 arms)
    
    int K = 3 * N;
    K = min(K, 240);
    
    vector<vector<int>> C(K, vector<int>(K, 0));
    
    // Assign each country i to position (3*i, 3*i) in a cross pattern
    for (int i = 1; i <= N; i++) {
        int base_r = (i - 1) * 3;
        int base_c = (i - 1) * 3;
        
        if (base_r + 2 < K && base_c + 2 < K) {
            // Create a cross pattern
            C[base_r + 1][base_c] = i;     // Top
            C[base_r][base_c + 1] = i;     // Left  
            C[base_r + 1][base_c + 1] = i; // Center
            C[base_r + 2][base_c + 1] = i; // Right
            C[base_r + 1][base_c + 2] = i; // Bottom
        }
    }
    
    // Fill remaining cells with country 1 (to ensure no empty cells)
    for (int r = 0; r < K; r++) {
        for (int c = 0; c < K; c++) {
            if (C[r][c] == 0) {
                C[r][c] = 1;
            }
        }
    }
    
    // Create edges by connecting adjacent countries
    for (int e = 0; e < M; e++) {
        int u = A[e];
        int v = B[e];
        
        int base_u_r = (u - 1) * 3 + 1;
        int base_u_c = (u - 1) * 3 + 1;
        int base_v_r = (v - 1) * 3 + 1;
        int base_v_c = (v - 1) * 3 + 1;
        
        // Connect u and v by extending arms toward each other
        if (base_u_r < base_v_r && base_u_c < K - 1) {
            // u is above v, extend u downward
            C[base_u_r + 1][base_u_c] = u;
            if (base_u_r + 2 < K) C[base_u_r + 2][base_u_c] = v;
        } else if (base_u_r > base_v_r && base_u_r > 0) {
            // u is below v, extend u upward  
            C[base_u_r - 1][base_u_c] = u;
            if (base_u_r - 2 >= 0) C[base_u_r - 2][base_u_c] = v;
        }
        
        if (base_u_c < base_v_c && base_u_r < K - 1) {
            // u is left of v, extend u rightward
            C[base_u_r][base_u_c + 1] = u;
            if (base_u_c + 2 < K) C[base_u_r][base_u_c + 2] = v;
        } else if (base_u_c > base_v_c && base_u_c > 0) {
            // u is right of v, extend u leftward
            C[base_u_r][base_u_c - 1] = u;
            if (base_u_c - 2 >= 0) C[base_u_r][base_u_c - 2] = v;
        }
    }
    
    // Optimization for better K/N ratio: Try smaller grid
    if (N <= 10) {
        // For small N, try a more compact 2D arrangement
        K = N + M / N + 2;
        K = max(K, 2);
        K = min(K, 240);
        
        C.assign(K, vector<int>(K, 1));
        
        // Place countries in a spiral or grid pattern
        int r = 0, c = 0;
        for (int i = 1; i <= N; i++) {
            if (c < K) {
                C[r][c] = i;
                c++;
                if (c >= K) {
                    c = 0;
                    r++;
                }
            }
        }
        
        // Add adjacencies
        for (int e = 0; e < M; e++) {
            int u = A[e];
            int v = B[e];
            bool found = false;
            
            // Find where u is and place v adjacent
            for (int i = 0; i < K && !found; i++) {
                for (int j = 0; j < K && !found; j++) {
                    if (C[i][j] == u) {
                        // Try to place v adjacent
                        if (i + 1 < K && (C[i + 1][j] == 1 || C[i + 1][j] == v)) {
                            C[i + 1][j] = v;
                            found = true;
                        } else if (j + 1 < K && (C[i][j + 1] == 1 || C[i][j + 1] == v)) {
                            C[i][j + 1] = v;
                            found = true;
                        }
                    }
                }
            }
        }
    }
    
    return C;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 7
• Subtask 4: 0 / 8
• Subtask 5: 0 / 14
• Subtask 6: 0 / 56