Submission #53137

#	Time	Username	Problem	Language	Result	Execution time	Memory
53137		SpaimaCarpatilor	Treasure (different grader from official contest) (CEOI13_treasure2)	C++17	80 / 100	6 ms	1356 KiB

treasure

#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 findTreasure (int N)
{
    int K = N / 2;
    for (int i=1; i<=K + 1; i++)
        for (int j=1; j<=K + 1; j++)
            s[i][j] = query (i, j, N, N);
    for (int i=1; i<=K; i++)
        for (int j=1; j<=K; j++)
            a[i][j] = s[i][j] - s[i + 1][j] - s[i][j + 1] + s[i + 1][j + 1];
    for (int i=1; i<=K + 1; i++)
        for (int j=K; j<=N; j++)
            s[i][j] = query (i, 1, N, j);
    for (int i=1; i<=K; i++)
        for (int j=K + 1; j<=N; j++)
            a[i][j] = s[i][j] - s[i + 1][j] - s[i][j - 1] + s[i + 1][j - 1];

    for (int i=K; i<=N; i++)
        for (int j=1; j<=K + 1; j++)
            s[i][j] = query (1, j, i, N);
    for (int i=K + 1; i<=N; i++)
        for (int j=1; j<=K; j++)
            a[i][j] = s[i][j] - s[i - 1][j] - s[i][j + 1] + s[i - 1][j + 1];
    for (int i=K; i<=N; i++)
        for (int j=K; j<=N; j++)
            s[i][j] = query (1, 1, i, j);
    for (int i=K + 1; i<=N; i++)
        for (int j=K + 1; j<=N; j++)
            a[i][j] = s[i][j] - s[i - 1][j] - s[i][j - 1] + s[i - 1][j - 1];
    for (int i=1; i<=N; i++)
        for (int j=1; j<=N; j++)
            if (a[i][j] > 0)
                Report (i, j);
}

Compilation message (stderr)

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];
                                            ^~~~~
treasure.cpp:5:15: warning: 'K' defined but not used [-Wunused-variable]
 static int N, K, s[109][109], a[109][109], partS[109][109];
               ^
treasure.cpp:5:12: warning: 'N' defined but not used [-Wunused-variable]
 static int N, K, s[109][109], a[109][109], partS[109][109];
            ^

• Subtask 1: 80 / 100