oj.uz

답안 #503069

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
503069 2022-01-07T05:38:12 Z bang627 보물 찾기 (CEOI13_treasure2) C++14
0 / 100
 13 ms 484 KB 
#include "treasure.h"
#include <iostream>

using namespace std;
void solution(int x1, int y1, int x2, int y2, int** board);
void findTreasure (int N) {
    int** board = new int* [N];
    for (int i = 0; i < N; i++) board[i] = new int [N];
    solution(1, 1, N, N, board);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << board[i][j] << " ";
            if (board[i][j] == 1) Report(i + 1, j + 1);
        }
        cout << endl;
    }
    //if(cnt > 0) Report (1, 1);
}
void solution(int x1, int y1, int x2, int y2,int **board) {
    cout << x1 << " " << y1 << "~" << x2 << " " << y2 << endl;
    int dx = x2 - x1 + 1, dy = y2 - y1 + 1;
    int cnt1 = countTreasure(x1, y1, x2, y2);
    if (cnt1 == 0) {
        for (int i = x1; i <= x2; i++) for (int j = y1; j <= y2; j++) board[i - 1][j - 1] = 0;
        return;
    }
    if (cnt1 == dx * dy) {
        for (int i = x1; i <= x2; i++) for (int j = y1; j <= y2; j++) board[i - 1][j - 1] = 1;
        return;
    }
    if (dx >= dy) {
        int mx = int((x1 + x2) / 2);
        int cnt2 = countTreasure(x1, y1, mx, y2);        
        int cnt3 = cnt1 - cnt2;
        if (cnt2 == 0) for (int i = x1; i <= mx; i++) for (int j = y1; j <= y2; j++) board[i - 1][j - 1] = 0;
        else if (cnt2 == (mx - x1 + 1) * dy) for (int i = x1; i <= mx; i++) for (int j = y1; j <= y2; j++) board[i - 1][j - 1] = 1;
        else solution(x1, y1, mx, y2,board);

        if (cnt3 == 0) for (int i = mx + 1; i<=x2; i++) for (int j = y1; j <= y2; j++) board[i - 1][j - 1] = 0;
        else if (cnt3 == (x2-mx) * dy) for (int i = mx + 1; i <= x2; i++) for (int j = y1; j <= y2; j++) board[i - 1][j - 1] = 1;
        else solution(mx+1, y1, x2, y2,board);
    }
    else {
        int my = int((y1 + y2) / 2);
        int cnt2 = countTreasure(x1, y1, x2, my);
        int cnt3 = cnt1 - cnt2;
        if (cnt2 == 0) for (int i = x1; i <= x2; i++) for (int j = y1; j <= my; j++) board[i - 1][j - 1] = 0;
        else if (cnt2 == (my- y1 + 1) * dx) for (int i = x1; i <= x2; i++) for (int j = y1; j <= my; j++) board[i - 1][j - 1] = 1;
        else solution(x1, y1, x2, my, board);

        if (cnt3 == 0) for (int i = x1; i <= x2; i++) for (int j = my+1; j <= y2; j++) board[i - 1][j - 1] = 0;
        else if (cnt3 == (y2-my) * dx) for (int i = x1; i <= x2; i++) for (int j = my+1; j <= y2; j++) board[i - 1][j - 1] = 1;
        else solution(x1, my+1, x2, y2, board);
    }
}

Subtask #1
0.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 204 KB Invalid Access
2 Incorrect 0 ms 204 KB Invalid Access
3 Incorrect 0 ms 204 KB Invalid Access
4 Incorrect 0 ms 204 KB Invalid Access
5 Incorrect 4 ms 332 KB Invalid Access
6 Incorrect 5 ms 332 KB Invalid Access
7 Incorrect 2 ms 332 KB Invalid Access
8 Incorrect 2 ms 332 KB Invalid Access
9 Incorrect 13 ms 424 KB Invalid Access
10 Incorrect 12 ms 484 KB Invalid Access