제출 #94707

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
94707		rhdmstjr	보물 찾기 (CEOI13_treasure2)	C++11	41 / 100	2 ms	380 KiB

treasure

#include "treasure.h"

#include <vector>
using namespace std;

#define II  pair<int,int>

struct Rect{
    II topLeft; // <y, x>
    II bottomRight;
    int size() {
        return (bottomRight.first - topLeft.first + 1) * (bottomRight.second - topLeft.second + 1);
    }
};

void splitRect(Rect &in, Rect &out1, Rect &out2) {
    int h = in.bottomRight.first - in.topLeft.first + 1;
    int w = in.bottomRight.second - in.topLeft.second + 1;

    if (w <= h) {
        int midR = (in.bottomRight.first + in.topLeft.first) >> 1;
        out1 = Rect{II(in.topLeft.first, in.topLeft.second), II(midR, in.bottomRight.second)};
        out2 = Rect{II(midR + 1, in.topLeft.second), II(in.bottomRight.first, in.bottomRight.second)};
    }else {
        int midC = (in.bottomRight.second + in.topLeft.second) >> 1; 
        out1 = Rect{II(in.topLeft.first, in.topLeft.second), II(in.bottomRight.first, midC)};
        out2 = Rect{II(in.topLeft.first, midC + 1), II(in.bottomRight.first, in.bottomRight.second)};
    }
}

int savedPntLen;
II savedPnt[10004];

void reportAll(Rect &rect) {
    for(int r = rect.topLeft.first; r <= rect.bottomRight.first; r++) {
        for(int c = rect.topLeft.second; c <= rect.bottomRight.second; c++) {
            // Report(r, c);
            savedPnt[savedPntLen++] = II(r, c);
        }
    }
}


void printRect(Rect r) {
    // printf("(%d, %d) -- (%d, %d)\n", r.topLeft.first, r.topLeft.second, r.bottomRight.first, r.bottomRight.second);
}

// return cnt
int checkRect(Rect r) {
    printRect(r);
    int cnt = countTreasure(r.topLeft.first, r.topLeft.second, r.bottomRight.first, r.bottomRight.second);

    if (cnt == r.size()) {
        // 모두 report
        reportAll(r);
        return cnt;
    }
    if (cnt == 0) return 0;

    Rect r1, r2;
    splitRect(r, r1, r2);
    // 

    // printf("cnt: %d\n", cnt);
    printRect(r1);
    printRect(r2);

    int cnt1 = checkRect(r1);
    // printf("cnt1: %d\n", cnt1);

    // return 0;
    int cnt2 = cnt - cnt1;
    // printf("cnt2: %d\n", cnt2);
    if (cnt2 == r2.size()) {
        reportAll(r2);
    } else {
        if (cnt2 == 0) {

        }else{
            checkRect(r2);
        }
    }
    

    return cnt;
}

void callSavedReport() {
    for(int i = 0; i < savedPntLen; i++) {
        Report(savedPnt[i].first, savedPnt[i].second);
    }
}

void findTreasure (int N) {
    savedPntLen = 0;

    checkRect(Rect{II(1, 1), II(N, N)});

    callSavedReport();
}

• Subtask 1: 41 / 100