oj.uz

Submission #680605

# Submission time Handle Problem Language Result Execution time Memory
680605 2023-01-11T10:40:50 Z peijar Treasure (different grader from official contest) (CEOI13_treasure2) C++17
100 / 100
 1 ms 340 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);
}

Subtask #1
100.0 / 100.0

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