oj.uz

Submission #48967

# Submission time Handle Problem Language Result Execution time Memory
48967 2018-05-20T16:15:37 Z Benq Treasure (different grader from official contest) (CEOI13_treasure2) C++14
100 / 100
 2 ms 564 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

#include "treasure.h"

int cum[101][101], N;

/*int ans = 0, tmp[101][101];

void Report(int a, int b) {
    assert(tmp[a][b] == 1);
    // cout << a << " " << b << " " << tmp[a][b] << "\n";
}

int countTreasure(int a1, int b1, int a2, int b2) {
    assert (a1 <= a2 && b1 <= b2);
    int z = 0;
    FOR(i,a1,a2+1) FOR(j,b1,b2+1) z += tmp[i][j];
    ans += 50*50+1-(a2-a1+1)*(b2-b1+1);
    return z;
}*/

int query(int a, int b) {
    return cum[a][b]-cum[a-1][b]-cum[a][b-1]+cum[a-1][b-1];
}

void smart(int x, int y) {
    if (x > N-x) {
        if (y > N-y) {
            cum[x][y] = countTreasure(1,1,x,y);
        } else {
            cum[x][y] = cum[x][N]-countTreasure(1,y+1,x,N);
        }
    } else {
        if (y > N-y) {
            cum[x][y] = cum[N][y]-countTreasure(x+1,1,N,y);
        } else {
            cum[x][y] = cum[x][N]+cum[N][y]-cum[N][N]+countTreasure(x+1,y+1,N,N);
        }
    }
}
void findTreasure (int n) {
    N = n;
    cum[N][N] = countTreasure(1,1,N,N);
    FOR(i,1,N) {
        if (i > N-i) {
            cum[i][N] = countTreasure(1,1,i,N);
            cum[N][i] = countTreasure(1,1,N,i);
        } else {
            cum[i][N] = cum[N][N]-countTreasure(i+1,1,N,N);
            cum[N][i] = cum[N][N]-countTreasure(1,i+1,N,N);
        }
    }
    FOR(i,1,N) FOR(j,1,N) smart(i,j);
    FOR(i,1,N+1) FOR(j,1,N+1) if (query(i,j)) 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)");
                   ~~~~~~~~~~~~~~~^~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct - N = 5, K = 289, score = 10
2 Correct 2 ms 356 KB Output is correct - N = 10, K = 4475, score = 10
3 Correct 2 ms 408 KB Output is correct - N = 15, K = 22289, score = 10
4 Correct 2 ms 484 KB Output is correct - N = 16, K = 28928, score = 10
5 Correct 2 ms 544 KB Output is correct - N = 55, K = 4005289, score = 10
6 Correct 2 ms 564 KB Output is correct - N = 66, K = 8305803, score = 10
7 Correct 2 ms 564 KB Output is correct - N = 77, K = 15383161, score = 10
8 Correct 2 ms 564 KB Output is correct - N = 88, K = 26244416, score = 10
9 Correct 2 ms 564 KB Output is correct - N = 99, K = 42032201, score = 10
10 Correct 2 ms 564 KB Output is correct - N = 100, K = 43760000, score = 10