提出 #73317509

---

ソースコード 拡げる

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int h, w, id;
} Piece;

typedef struct {
    long long x, y;
} Result;

// Comparator for sorting by height (descending) then width
int compareH(const void* a, const void* b) {
    Piece* p1 = (Piece*)a;
    Piece* p2 = (Piece*)b;
    if (p1->h != p2->h) return p2->h - p1->h;
    return p2->w - p1->w;
}

// Comparator for sorting by width (descending) then height
int compareW(const void* a, const void* b) {
    Piece* p1 = (Piece*)a;
    Piece* p2 = (Piece*)b;
    if (p1->w != p2->w) return p2->w - p1->w;
    return p2->h - p1->h;
}

int main() {
    long long H, W;
    int N;
    if (scanf("%lld %lld %d", &H, &W, &N) != 3) return 0;

    Piece *byH = malloc(sizeof(Piece) * N);
    Piece *byW = malloc(sizeof(Piece) * N);
    int *used = calloc(N, sizeof(int));
    Result *results = malloc(sizeof(Result) * N);

    for (int i = 0; i < N; i++) {
        int h, w;
        scanf("%d %d", &h, &w);
        byH[i] = (Piece){h, w, i};
        byW[i] = (Piece){h, w, i};
    }

    qsort(byH, N, sizeof(Piece), compareH);
    qsort(byW, N, sizeof(Piece), compareW);

    long long currH = H, currW = W;
    long long currX = 1, currY = 1;
    int ptrH = 0, ptrW = 0;

    for (int i = 0; i < N; i++) {
        // Look for a piece that matches current bounding box height
        while (ptrH < N && (used[byH[ptrH].id] || byH[ptrH].h > currH)) ptrH++;
        
        if (ptrH < N && byH[ptrH].h == currH) {
            int idx = byH[ptrH].id;
            results[idx].x = currX;
            results[idx].y = currY;
            currY += byH[ptrH].w;
            currW -= byH[ptrH].w;
            used[idx] = 1;
        } else {
            // Otherwise, find a piece that matches current bounding box width
            while (ptrW < N && (used[byW[ptrW].id] || byW[ptrW].w > currW)) ptrW++;
            
            int idx = byW[ptrW].id;
            results[idx].x = currX;
            results[idx].y = currY;
            currX += byW[ptrW].h;
            currH -= byW[ptrW].h;
            used[idx] = 1;
        }
    }

    for (int i = 0; i < N; i++) {
        printf("%lld %lld\n", results[i].x, results[i].y);
    }

    free(byH);
    free(byW);
    free(used);
    free(results);
    return 0;
}

提出情報

ジャッジ結果