oj.uz

Submission #94991

# Submission time Handle Problem Language Result Execution time Memory
94991 2019-01-26T14:43:29 Z popovicirobert Treasure (different grader from official contest) (CEOI13_treasure2) C++14
80 / 100
 2 ms 420 KB 
#include "treasure.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100;

bool mat[MAXN + 1][MAXN + 1];
int cnt_c[MAXN + 1], cnt_l[MAXN + 1];

void findTreasure (int n) {
    int i, j;

    int last = countTreasure((n + 1) / 2 + 1, 1, n, n);
    for(i = (n + 1) / 2; i >= 1; i--) {
        cnt_l[i] = countTreasure(i, 1, n, n) - last;
        last += cnt_l[i];
    }
    last = countTreasure(1, 1, (n + 1) / 2, n);
    for(i = (n + 1) / 2 + 1; i <= n; i++) {
        cnt_l[i] = countTreasure(1, 1, i, n) - last;
        last += cnt_l[i];
    }

    last = countTreasure(1, (n + 1) / 2 + 1, n, n);
    for(i = (n + 1) / 2; i >= 1; i--) {
        cnt_c[i] = countTreasure(1, i, n, n) - last;
        last += cnt_c[i];
    }
    last = countTreasure(1, 1, n, (n + 1) / 2);
    for(i = (n + 1) / 2 + 1; i <= n; i++) {
        cnt_c[i] = countTreasure(1, 1, n, i) - last;
        last += cnt_c[i];
    }

    int sum_l = 0;
    for(i = 1; i <= n; i++) {
        sum_l += cnt_l[i];
    }
    for(i = 1; i <= (n + 1) / 2; i++) {
        int cnt = 0, tot = 0, nr = 0;
        for(j = 1; j < (n + 1) / 2; j++) {
            int cur = countTreasure(i + 1, j + 1, n, n);
            if(sum_l - cur - cnt < cnt_l[i] - nr + cnt_c[j]) {
                mat[i][j] = 1;
                tot++, nr++;
            }
            cnt += cnt_c[j];
        }
        cnt = nr = 0;
        for(j = n; j > (n + 1) / 2; j--) {
            int cur = countTreasure(i + 1, 1, n, j - 1);
            if(sum_l - cur - cnt < cnt_l[i] - nr + cnt_c[j]) {
                mat[i][j] = 1;
                tot++, nr++;
            }
            cnt += cnt_c[j];
        }
        mat[i][(n + 1) / 2] = cnt_l[i] - tot;
        for(j = 1; j <= n; j++) {
            cnt_c[j] -= mat[i][j];
        }
        sum_l -= cnt_l[i];
    }

    /*for(i = 1; i <= n; i++) {
        for(j = 1; j <= n; j++) {
            cerr << mat[i][j];
        }
        cerr << "\n";
    }
    cerr << "\n";*/

    sum_l = 0;
    for(i = 1; i <= n; i++) {
        sum_l += cnt_l[i];
        for(j = 1; j <= n; j++) {
            cnt_c[j] += mat[i][j];
        }
    }
    for(i = n; i > (n + 1) / 2; i--) {
        int cnt = 0, tot = 0, nr = 0;
        for(j = 1; j < (n + 1) / 2; j++) {
            int cur = countTreasure(1, j + 1, i - 1, n);
            if(sum_l - cur - cnt < cnt_l[i] - nr + cnt_c[j]) {
                mat[i][j] = 1;
                tot++, nr++;
            }
            cnt += cnt_c[j];
        }
        cnt = nr = 0;
        for(j = n; j > (n + 1) / 2; j--) {
            int cur = countTreasure(1, 1, i - 1, j - 1);
            if(sum_l - cur - cnt < cnt_l[i] - nr + cnt_c[j]) {
                mat[i][j] = 1;
                tot++, nr++;
            }
            cnt += cnt_c[j];
        }
        mat[i][(n + 1) / 2] = cnt_l[i] - tot;
        for(j = 1; j <= n; j++) {
            cnt_c[j] -= mat[i][j];
        }
        sum_l -= cnt_l[i];
    }

    for(i = 1; i <= n; i++) {
        for(j = 1; j <= n; j++) {
            if(mat[i][j]) {
                Report(i, j);
            }
        }
    }
}

Subtask #1
80.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 376 KB Output is partially correct - N = 5, K = 400, score = 8
2 Partially correct 2 ms 376 KB Output is partially correct - N = 10, K = 5164, score = 8
3 Partially correct 2 ms 248 KB Output is partially correct - N = 15, K = 24620, score = 8
4 Partially correct 2 ms 380 KB Output is partially correct - N = 16, K = 31636, score = 8
5 Partially correct 2 ms 296 KB Output is partially correct - N = 55, K = 4112000, score = 8
6 Partially correct 2 ms 376 KB Output is partially correct - N = 66, K = 8487736, score = 8
7 Partially correct 2 ms 376 KB Output is partially correct - N = 77, K = 15673792, score = 8
8 Partially correct 2 ms 376 KB Output is partially correct - N = 88, K = 26674300, score = 8
9 Partially correct 2 ms 420 KB Output is partially correct - N = 99, K = 42647354, score = 8
10 Partially correct 2 ms 376 KB Output is partially correct - N = 100, K = 44390104, score = 8