Submission #53133

#	Time	Username	Problem	Language	Result	Execution time	Memory
53133		SpaimaCarpatilor	Treasure (different grader from official contest) (CEOI13_treasure2)	C++17	80 / 100	6 ms	1404 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)) return mp[curr];
    int x = countTreasure (a, b, c, d);
    mp[curr] = x;
    return x;
}

void upRight ()
{
    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];
}

void downLeft ()
{
    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];
}

void buildPartS ()
{
    for (int i=1; i<=N; i++)
        for (int j=1; j<=N; j++)
            partS[i][j] = partS[i - 1][j] + partS[i][j - 1] - partS[i - 1][j - 1] + a[i][j];
}

int getPartSum (int a1, int b1, int a2, int b2)
{
    if (a1 > a2 || b1 > b2) return 0;
    return partS[a2][b2] - partS[a1 - 1][b2] - partS[a2][b1 - 1] + partS[a1 - 1][b1 - 1];
}

void upLeft ()
{
    int X = query (K + 1, K + 1, N, N);
    for (int i=1; i<=K; i++)
        for (int j=1; j<=K; j++)
            s[i][j] = query (i, j, N, N);
    for (int j=1; j<=K + 1; j++)
        s[K + 1][j] = getPartSum (K + 1, j, N, K) + X;
    for (int i=1; i<=K + 1; i++)
        s[i][K + 1] = getPartSum (i, K + 1, K, N) + X;
    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];
}

void downRight ()
{
    int X = 0;
    for (int i=1; i<=K; i++)
        for (int j=1; j<=K; j++)
            X += a[i][j];
    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 j=K; j<=N; j++)
        s[K][j] = getPartSum (1, K + 1, K, j) + X;
    for (int i=K; i<=N; i++)
        s[i][K] = getPartSum (K + 1, 1, i, K) + X;
    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];
}

void findTreasure (int nn)
{
    N = nn, K = N / 2;
    downLeft (), upRight ();
    buildPartS ();
    upLeft (), downRight ();
    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)");
                   ~~~~~~~~~~~~~~~^~~~

• Subtask 1: 80 / 100