oj.uz

Submission #503066

# Submission time Handle Problem Language Result Execution time Memory
503066 2022-01-07T05:14:21 Z bang627 Treasure (different grader from official contest) (CEOI13_treasure2) C++14
0 / 100
 1 ms 384 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 264 KB Error - not all of the treasure cells have been reported
2 Incorrect 1 ms 280 KB Error - not all of the treasure cells have been reported
3 Incorrect 0 ms 204 KB Error - not all of the treasure cells have been reported
4 Incorrect 0 ms 204 KB Error - not all of the treasure cells have been reported
5 Incorrect 1 ms 384 KB Error - not all of the treasure cells have been reported
6 Incorrect 1 ms 324 KB Error - not all of the treasure cells have been reported
7 Incorrect 1 ms 332 KB Error - not all of the treasure cells have been reported
8 Incorrect 0 ms 280 KB Error - not all of the treasure cells have been reported
9 Incorrect 1 ms 332 KB Error - not all of the treasure cells have been reported
10 Incorrect 1 ms 332 KB Error - not all of the treasure cells have been reported