oj.uz

Submission #53142

# Submission time Handle Problem Language Result Execution time Memory
53142 2018-06-28T19:55:47 Z SpaimaCarpatilor Treasure (different grader from official contest) (CEOI13_treasure2) C++17
100 / 100
 9 ms 1672 KB 
#include "treasure.h"
#include<bits/stdc++.h>
using namespace std;

static int N, K, s[109][109], a[109][109], partS[109][109];
static map < pair < pair < int, int >, pair < int, int > >, int > mp;

int query (int a, int b, int c, int d)
{
    pair < pair < int, int >, pair < int, int > > curr = {{a, b}, {c, d}};
    if (mp.count (curr))
    {
        //printf ("(%d %d) (%d, %d)\n", a, b, c, d);
        return mp[curr];
    }
    int x = countTreasure (a, b, c, d);
    mp[curr] = x;
    return x;
}

void addData (int i, int j)
{
    pair < pair < int, int >, pair < int, int > > curr = {{1, 1}, {i, j}};
    if (!mp.count (curr))
        mp[curr] = s[i][j];
}

int sum (int a1, int b1, int a2, int b2)
{
    return s[a2][b2] - s[a1 - 1][b2] - s[a2][b1 - 1] + s[a1 - 1][b1 - 1];
}

void findTreasure (int nn)
{
    N = nn, K = N / 2;
    for (int i=1; i<=N; i++)
    {
        if (i > K)
            s[i][N] = query (1, 1, i, N),
            s[N][i] = query (1, 1, N, i);
        else
            s[i][N] = query (1, 1, N, N) - query (i + 1, 1, N, N),
            s[N][i] = query (1, 1, N, N) - query (1, i + 1, N, N),
            addData (i, N), addData (N, i);
    }
    for (int i=K + 1; i<=N; i++)
        for (int j=K + 1; j<=N; j++)
            s[i][j] = query (1, 1, i, j);
    for (int i=K + 1; i<=N; i++)
        for (int j=1; j<=K; j++)
            s[i][j] = query (1, 1, i, N) - query (1, j + 1, i, N), addData (i, j);
    for (int i=1; i<=K; i++)
        for (int j=K + 1; j<=N; j++)
            s[i][j] = query (1, 1, N, j) - query (i + 1, 1, N, j), addData (i, j);
    for (int i=1; i<=K; i++)
        for (int j=1; j<=K; j++)
            s[i][j] = s[N][N] - (sum (1, j + 1, N, N) + sum (i + 1, 1, N, N) - query (i + 1, j + 1, N, N)), addData (i, j);
    for (int i=1; i<=N; i++)
        for (int j=1; j<=N; j++)
        {
            a[i][j] = s[i][j] - s[i - 1][j] - s[i][j - 1] + s[i - 1][j - 1];
            if (a[i][j] > 0)
                Report (i, j);
        }
}

Compilation message

grader.c: In function 'int main()':
grader.c:63:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         my_assert(strlen(A[i]+1) == N, "each line of the map must contain N zeroes or ones (before loop)");
                   ~~~~~~~~~~~~~~~^~~~
treasure.cpp:5:44: warning: 'partS' defined but not used [-Wunused-variable]
 static int N, K, s[109][109], a[109][109], partS[109][109];
                                            ^~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct - N = 5, K = 289, score = 10
2 Correct 2 ms 488 KB Output is correct - N = 10, K = 4475, score = 10
3 Correct 2 ms 488 KB Output is correct - N = 15, K = 22289, score = 10
4 Correct 2 ms 488 KB Output is correct - N = 16, K = 28928, score = 10
5 Correct 4 ms 872 KB Output is correct - N = 55, K = 4005289, score = 10
6 Correct 5 ms 1136 KB Output is correct - N = 66, K = 8305803, score = 10
7 Correct 6 ms 1160 KB Output is correct - N = 77, K = 15383161, score = 10
8 Correct 7 ms 1416 KB Output is correct - N = 88, K = 26244416, score = 10
9 Correct 9 ms 1672 KB Output is correct - N = 99, K = 42032201, score = 10
10 Correct 8 ms 1672 KB Output is correct - N = 100, K = 43760000, score = 10