# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
48967 | Benq | Treasure (different grader from official contest) (CEOI13_treasure2) | C++14 | 2 ms | 564 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |