Submission #380792

# Submission time Handle Problem Language Result Execution time Memory
380792 2021-03-23T02:37:29 Z wp1270 Treasure (different grader from official contest) (CEOI13_treasure2) C++14
2 / 100
1 ms 364 KB
#include "treasure.h"
#define MAX_N 100

int front;
int rear;
int shouldBeHere[105][105] = { 0, };
typedef struct {
    int r1, c1, r2, c2, t;
}pos;
pos queue[MAX_N];

void queueInit(void) {
    front = 0;
    rear = 0;
}
int queueIsEmpty(void) {
    return (front == rear);
}
int queueIsFull(void) {
    if ((rear + 1) % MAX_N == front) {
        return 1;
    }
    else {
        return 0;
    }
}
int queueEnqueue(pos value) {
    if (queueIsFull()) {
        return 0;
    }
    queue[rear] = value;
    rear++;
    if (rear == MAX_N) {
        rear = 0;
    }

    return 1;
}
int queueDequeue(pos* value) {
    if (queueIsEmpty()) {
        return 0;
    }
    *value = queue[front];
    front++;
    if (front == MAX_N) {
        front = 0;
    }
    return 1;
}

void findTreasure(int N) {
    int cnt = countTreasure(1, 1, N, N);
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            shouldBeHere[i][j] = 0;
        }
    }
    if (cnt > 0) {
        queueInit();
        pos first;
        first.r1 = 1;
        first.c1 = 1;
        first.r2 = N;
        first.c2 = N;
        first.t = cnt;
        queueEnqueue(first);
        while (!queueIsEmpty()) {
            pos now;
            queueDequeue(&now);
            if (now.r1 == now.r2 && now.c1 == now.c2) {
                shouldBeHere[now.r1][now.c1] = 1;
            }
            else {
                int numT = now.t;
                int center_r = (now.r1 + now.r2) / 2;
                int center_c = (now.c1 + now.c2) / 2;
                int foundHere = 0;
                if (numT > 0) {
                    foundHere = countTreasure(now.r1, now.c1, center_r, center_c);
                    if (foundHere) {
                        pos left_up;
                        left_up.r1 = now.r1;
                        left_up.c1 = now.c1;
                        left_up.r2 = center_r;
                        left_up.c2 = center_c;
                        left_up.t = foundHere;
                        numT -= foundHere;
                        queueEnqueue(left_up);
                    }
                }
                if (numT > 0) {
                    if (now.c2 >= center_c + 1) {
                        foundHere = countTreasure(now.r1, center_c + 1, center_r, now.c2);
                        if (foundHere) {
                            pos right_up;
                            right_up.r1 = now.r1;
                            right_up.c1 = center_c + 1;
                            right_up.r2 = center_r;
                            right_up.c2 = now.c2;
                            right_up.t = foundHere;
                            numT -= foundHere;
                            queueEnqueue(right_up);
                        }
                    }
                }
                if (numT > 0) {
                    if (now.r2 >= center_r + 1) {
                        foundHere = countTreasure(center_r + 1, now.c1, now.r2, center_c);
                        if (foundHere) {
                            pos left_down;
                            left_down.r1 = center_r + 1;
                            left_down.c1 = now.c1;
                            left_down.r2 = now.r2;
                            left_down.c2 = center_c;
                            left_down.t = foundHere;
                            numT -= foundHere;
                            queueEnqueue(left_down);
                        }
                    }
                }
                if (numT > 0) {
                    foundHere = 0;
                    if (now.r2 >= center_r + 1 && now.c2 >= center_c + 1) {
                            pos right_down;
                            right_down.r1 = center_r + 1;
                            right_down.c1 = center_c + 1;
                            right_down.r2 = now.r2;
                            right_down.c2 = now.c2;
                            right_down.t = numT;
                            queueEnqueue(right_down);
                        
                    }
                }
              
            }
           
        
        }
    }
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (shouldBeHere[i][j]) {
                Report(i, j);
            }
        }
    }
}

/*
10
1011010101
1100010001
0100100101
0000101100
1111010100
0010100000
1101010001
0001010100
0101000100
1101010101
*/
# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 364 KB Output is partially correct - N = 5, K = 624, score = 1
2 Partially correct 0 ms 364 KB Output is partially correct - N = 10, K = 9723, score = 1
3 Incorrect 0 ms 364 KB Error - not all of the treasure cells have been reported
4 Incorrect 0 ms 364 KB Error - not all of the treasure cells have been reported
5 Incorrect 1 ms 364 KB Error - not all of the treasure cells have been reported
6 Incorrect 1 ms 364 KB Error - not all of the treasure cells have been reported
7 Incorrect 1 ms 364 KB Error - not all of the treasure cells have been reported
8 Incorrect 1 ms 364 KB Error - not all of the treasure cells have been reported
9 Incorrect 1 ms 364 KB Error - not all of the treasure cells have been reported
10 Incorrect 1 ms 364 KB Error - not all of the treasure cells have been reported