Submission #503066

#	Time	Username	Problem	Language	Result	Execution time	Memory
503066		bang627	Treasure (different grader from official contest) (CEOI13_treasure2)	C++14	0 / 100	1 ms	384 KiB

treasure

#include "treasure.h"
void solution(int x1, int y1, int x2, int y2, int** board);
void findTreasure (int N) {
    //int cnt = countTreasure(1, 1, N, 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++) if (board[i][j] == 1) Report(i+1, j+1);
    //if(cnt > 0) Report (1, 1);
}
void solution(int x1, int y1, int x2, int y2,int **board) {
    int dx = x2 - x1 + 1, dy = y2 - y1 + 1;
    if (dx >= dy) {
        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;
        }        
        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(x1, y1, mx, y2,board);
    }
    else {
        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;
        }
        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 / 100