Submission #1148829

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148829		andrejikus	방벽 (JOI15_walls)	C++20	0 / 100	13 ms	836 KiB

walls

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

using namespace std;

struct Barrier {
    int A, B, index;
};

// Function to compute the minimum movements for each barrier
vector<int> min_barrier_moves(int N, int M, vector<Barrier>& barriers, vector<int>& attacks) {
    // Sort barriers by their starting position (A)
    sort(barriers.begin(), barriers.end(), [](const Barrier &a, const Barrier &b) {
        return a.A < b.A;
    });

    // Sort attack positions
    sort(attacks.begin(), attacks.end());

    // Arrays to track A and B separately
    vector<int> A(N), B(N), moves(N, 0);
    for (int i = 0; i < N; i++) {
        A[i] = barriers[i].A;
        B[i] = barriers[i].B;
    }

    // Process each attack using binary search
    for (int P : attacks) {
        // Find the first barrier whose B >= P
        int idx = lower_bound(B.begin(), B.end(), P) - B.begin();

        // If an attack P is already covered by some barrier, continue
        if (idx < N && A[idx] <= P && P <= B[idx]) {
            continue;
        }

        // Find the best barrier to move (closest left or right)
        int left_idx = (idx > 0) ? idx - 1 : 0;
        int right_idx = (idx < N) ? idx : N - 1;

        if (left_idx >= 0 && abs(A[left_idx] - P) < abs(A[right_idx] - P)) {
            // Move left barrier
            moves[left_idx] += abs(A[left_idx] - P);
            A[left_idx] = P;
            B[left_idx] = P;
        } else {
            // Move right barrier
            moves[right_idx] += abs(A[right_idx] - P);
            A[right_idx] = P;
            B[right_idx] = P;
        }
    }

    // Store results in original barrier order
    vector<int> result(N);
    for (int i = 0; i < N; i++) {
        result[barriers[i].index] = moves[i];
    }
    
    return result;
}

int main() {
    int N, M;
    cin >> N >> M;

    vector<Barrier> barriers(N);
    vector<int> attacks(M);

    // Read barriers
    for (int i = 0; i < N; i++) {
        cin >> barriers[i].A >> barriers[i].B;
        barriers[i].index = i; // Store original index for output ordering
    }

    // Read attack positions
    for (int j = 0; j < M; j++) {
        cin >> attacks[j];
    }

    // Compute results
    vector<int> result = min_barrier_moves(N, M, barriers, attacks);

    // Print results
    for (int moves : result) {
        cout << moves << "\n";
    }

    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 45
• Subtask 3: 0 / 45