oj.uz

Submission #218185

# Submission time Handle Problem Language Result Execution time Memory
218185 2020-04-01T11:44:19 Z pichulia Treasure (different grader from official contest) (CEOI13_treasure2) C++11
56 / 100
 5 ms 384 KB 
#include "treasure.h"
//#include"header.h"
int result[10009][4];
int rl;
void dfs(int remain, int si, int ei, int sj, int ej) {
    if (ei < si)return;
    if (ej < sj)return;
    if (remain == (ei - si + 1) * (ej - sj + 1)) {
        result[rl][0] = si;
        result[rl][1] = ei;
        result[rl][2] = sj;
        result[rl][3] = ej;
        rl++;
        return;
    }
    if (remain == 0) {
        return;
    }
    if (si == ei) {
        int mj = (sj + ej) / 2;
        int ab = countTreasure(si + 1, sj + 1, ei + 1, mj + 1);
        dfs(ab, si, ei, sj, mj);
        dfs(remain - ab, si, ei, mj + 1, ej);
    }
    else if (sj == ej) {
        int mi = (si + ei) / 2;
        int ac = countTreasure(si + 1, sj + 1, mi + 1, ej + 1);
        dfs(ac, si, mi, sj, ej);
        dfs(remain - ac, mi + 1, ei, sj, ej);
    }
    else {
        int mi = (si + ei) / 2;
        int mj = (sj + ej) / 2;
        int ab = countTreasure(si + 1, sj + 1, ei + 1, mj + 1);
        if (ab == (ei - si + 1) * (mj - sj + 1)) {
            dfs(ab, si, ei, sj, mj);
            dfs(remain - ab, si, ei, mj + 1, ej);
            return;
        }
        int ac = countTreasure(si + 1, sj + 1, mi + 1, ej + 1);
        if (ac == (mi - si + 1) * (ej - sj + 1)) {
            dfs(ac, si, mi, sj, ej);
            dfs(remain - ac, mi + 1, ei, sj, ej);
            return;
        }
        int aa = countTreasure(si + 1, sj + 1, mi + 1, mj + 1);
        dfs(aa, si, mi, sj, mj);
        dfs(ab - aa, mi + 1, ei, sj, mj);
        dfs(ac - aa, si, mi, mj + 1, ej);
        dfs(remain - ab - ac + aa, mi + 1, ei, mj + 1, ej);
    }
}
void findTreasure(int N) {
    int cnt = countTreasure(1, 1, N, N);
    if (cnt == 0)return;
    else {
        rl = 0;
        dfs(cnt, 0, N - 1, 0, N - 1);
        while (rl--) {
            for (int i = result[rl][0]; i <= result[rl][1]; i++) {
                for (int j = result[rl][2]; j <= result[rl][3]; j++) {
                    Report(i + 1, j + 1);
                }
            }
        }
    }
}

Subtask #1
56.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 256 KB Output is partially correct - N = 5, K = 412, score = 8
2 Partially correct 4 ms 256 KB Output is partially correct - N = 10, K = 7131, score = 4
3 Correct 4 ms 256 KB Output is correct - N = 15, K = 17902, score = 10
4 Correct 4 ms 384 KB Output is correct - N = 16, K = 18140, score = 10
5 Partially correct 4 ms 384 KB Output is partially correct - N = 55, K = 7369778, score = 1
6 Partially correct 5 ms 384 KB Output is partially correct - N = 66, K = 15852780, score = 1
7 Correct 4 ms 384 KB Output is correct - N = 77, K = 5897772, score = 10
8 Correct 5 ms 384 KB Output is correct - N = 88, K = 7316353, score = 10
9 Partially correct 5 ms 384 KB Output is partially correct - N = 99, K = 76713566, score = 1
10 Partially correct 5 ms 384 KB Output is partially correct - N = 100, K = 81021012, score = 1