Submission #53142

#	Time	Username	Problem	Language	Result	Execution time	Memory
53142		SpaimaCarpatilor	Treasure (different grader from official contest) (CEOI13_treasure2)	C++17	100 / 100	9 ms	1672 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 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 (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];
                                            ^~~~~

• Subtask 1: 100 / 100