QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#93982 | #5818. Macaron | HaccerKat | 100 ✓ | 72ms | 18216kb | C++20 | 8.0kb | 2023-04-04 13:39:10 | 2023-04-04 13:39:12 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
template<typename T>
int SIZE(T (&t)){
return t.size();
}
template<typename T, size_t N>
int SIZE(T (&t)[N]){
return N;
}
string to_string(char t){
return "'" + string({t}) + "'";
}
string to_string(bool t){
return t ? "true" : "false";
}
string to_string(const string &t, int x1=0, int x2=1e9){
string ret = "";
for(int i = min(x1,SIZE(t)), _i = min(x2,SIZE(t)-1); i <= _i; ++i){
ret += t[i];
}
return '"' + ret + '"';
}
string to_string(const char* t){
string ret(t);
return to_string(ret);
}
template<size_t N>
string to_string(const bitset<N> &t, int x1=0, int x2=1e9){
string ret = "";
for(int i = min(x1,SIZE(t)); i <= min(x2,SIZE(t)-1); ++i){
ret += t[i] + '0';
}
return to_string(ret);
}
template<typename T, typename... Coords>
string to_string(const T (&t), int x1=0, int x2=1e9, Coords... C);
template<typename T, typename S>
string to_string(const pair<T, S> &t){
return "(" + to_string(t.first) + ", " + to_string(t.second) + ")";
}
template<typename T, typename... Coords>
string to_string(const T (&t), int x1, int x2, Coords... C){
string ret = "[";
x1 = min(x1, SIZE(t));
auto e = begin(t);
advance(e,x1);
for(int i = x1, _i = min(x2,SIZE(t)-1); i <= _i; ++i){
ret += to_string(*e, C...) + (i != _i ? ", " : "");
e = next(e);
}
return ret + "]";
}
template<int Index, typename... Ts>
struct print_tuple{
string operator() (const tuple<Ts...>& t) {
string ret = print_tuple<Index - 1, Ts...>{}(t);
ret += (Index ? ", " : "");
return ret + to_string(get<Index>(t));
}
};
template<typename... Ts>
struct print_tuple<0, Ts...> {
string operator() (const tuple<Ts...>& t) {
return to_string(get<0>(t));
}
};
template<typename... Ts>
string to_string(const tuple<Ts...>& t) {
const auto Size = tuple_size<tuple<Ts...>>::value;
return print_tuple<Size - 1, Ts...>{}(t);
}
void dbgr(){;}
template<typename Heads, typename... Tails>
void dbgr(Heads H, Tails... T){
cout << to_string(H) << " | ";
dbgr(T...);
}
void dbgs(){;}
template<typename Heads, typename... Tails>
void dbgs(Heads H, Tails... T){
cout << H << " ";
dbgs(T...);
}
/*
formatted functions:
*/
/*
consider __VA_ARGS__ as a whole:
dbgv() prints values only
dbg() prints name and values
*/
#define dbgv(...) cout << to_string(__VA_ARGS__) << endl;
#define dbg(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgv(__VA_ARGS__);
//#define dbg(...)
/*
consider __VA_ARGS__ as a sequence of arguments:
dbgr() prints values only
dbgm() prints names and values
*/
#define dbgr(...) dbgr(__VA_ARGS__); cout << endl;
#define dbgm(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgr(__VA_ARGS__);
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
/*
000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000
0000000
0000000
0000000
0000000
0000000
0000000
0000000
0000000
0000000
0000000
0000000
0000000
0000000
0000000
0000000
0000000
0000000
0000000
0000000
0000000
DO IT NOW!!!
*/
// using u128 = __uint128_t;
// using i128 = __int128;
const int mod = 1000000007;
const int N = 1005;
const int LOG = 20;
const int inf = 1e9;
const double eps = 1e-11;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
string s;
int n, m, k, qq, r, xs, ys;
bool vis[N][N], a[N][N], reachable[N][N];
int fromtop[N][N], frombot[N][N], pref[N][N];
void solve() {
cin >> n >> m >> r >> xs >> ys >> k;
for (int i = 0; i <= n + 1; i++) {
for (int j = 0; j <= m + 1; j++) {
if (i == 0 || i == n + 1 || j == 0 || j == m + 1) {
a[i][j] = true;
}
fromtop[i][j] = inf, fromtop[i][j] = inf;
}
}
for (int i = 0; i < k; i++) {
int x, y;
cin >> x >> y;
a[x][y] = true;
}
for (int j = 0; j <= m + 1; j++) {
for (int i = 0; i <= n + 1; i++) {
if (i != 0) fromtop[i][j] = fromtop[i - 1][j] + 1;
if (a[i][j]) fromtop[i][j] = 0;
}
for (int i = n + 1; i >= 0; i--) {
if (i != n + 1) frombot[i][j] = frombot[i + 1][j] + 1;
if (a[i][j]) frombot[i][j] = 0;
int dis = min(fromtop[i][j], frombot[i][j]);
if (dis * dis >= r) continue;
int rr = sqrt(r - dis * dis - 1);
pref[i][max(1, j - rr)]++, pref[i][min(j + rr + 1, m + 1)]--;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
pref[i][j] += pref[i][j - 1];
if (pref[i][j] == 0) reachable[i][j] = true;
}
}
// dbg(fromtop);
// dbg(reachable);
queue<pi> q;
q.push({xs, ys});
int out = 1;
vis[xs][ys] = true;
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (!vis[nx][ny] && reachable[nx][ny]) {
vis[nx][ny] = true, out++;
q.push({nx, ny});
}
}
}
cout << out << "\n";
/*
000000000000 000000000000
000000000000 000000000000
000000000000 000000000000
000000000000 000000000000
000000000000 000000000000
000000000000 000000000000
000000000000 000000000000
000000000000 000000000000
000000000000 000000000000
000000000000 000000000000
000000000000 000000000000
000000000000 000000000000
000000000000 000000000000
000000000000 000000000000
000000000000 000000000000
000000000000 000000000000
000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000
*/
}
int32_t main() {
std::ios::sync_with_stdio(false);
cin.tie(NULL);
solve();
}
詳細信息
Test #1:
score: 10
Accepted
time: 2ms
memory: 9568kb
input:
11 11 5 9 7 4 1 10 1 11 8 3 8 4
output:
37
result:
ok single line: '37'
Test #2:
score: 10
Accepted
time: 36ms
memory: 18156kb
input:
999 999 3000 340 211 25 230 432 513 610 514 610 360 56 360 55 474 319 474 318 687 476 687 477 204 142 205 142 206 142 207 142 244 511 243 511 242 511 241 511 32 652 32 653 32 654 32 655 197 976 539 579 540 579 540 578
output:
724629
result:
ok single line: '724629'
Test #3:
score: 10
Accepted
time: 29ms
memory: 18136kb
input:
1000 1000 5000 748 173 24 944 654 943 654 944 653 942 654 941 654 941 655 942 655 940 655 939 655 938 655 939 656 938 656 635 128 636 128 634 128 635 127 637 128 633 128 632 128 633 127 631 128 630 128 629 128 628 128
output:
716645
result:
ok single line: '716645'
Test #4:
score: 10
Accepted
time: 31ms
memory: 18060kb
input:
1000 1000 10000 668 126 30 9 589 39 505 165 527 185 25 211 383 231 699 235 849 291 839 317 955 319 627 355 79 355 117 365 521 447 253 473 721 515 161 517 157 587 465 627 849 641 515 729 893 775 81 783 583 813 1 839 699 869 215 931 365 937 975 941 47 965 249
output:
192418
result:
ok single line: '192418'
Test #5:
score: 10
Accepted
time: 0ms
memory: 13912kb
input:
50 50 30 36 40 11 50 41 29 16 31 23 48 9 27 22 8 33 9 33 1 40 3 39 27 21 29 30
output:
1200
result:
ok single line: '1200'
Test #6:
score: 10
Accepted
time: 0ms
memory: 10024kb
input:
100 100 300 69 24 17 32 34 33 34 31 34 40 55 32 10 98 77 97 77 96 77 81 71 19 69 87 66 88 66 88 67 100 38 100 37 19 89 13 48
output:
1730
result:
ok single line: '1730'
Test #7:
score: 10
Accepted
time: 29ms
memory: 18036kb
input:
1000 1000 5000 845 228 41 13 132 12 132 13 133 13 131 11 132 12 133 14 131 11 131 908 888 907 888 401 736 350 495 350 494 349 494 348 494 349 493 348 495 350 493 347 495 348 496 351 493 349 496 348 497 351 492 351 491 859 937 295 732 295 733 151 720 152 720 151 721 152 721 151 722 37 291 675 123 676...
output:
646861
result:
ok single line: '646861'
Test #8:
score: 10
Accepted
time: 36ms
memory: 18168kb
input:
1000 1000 10000 845 168 7949 901 901 901 902 901 903 901 904 901 905 901 906 901 909 901 911 901 912 901 913 901 914 901 915 901 916 901 917 901 918 901 919 901 920 901 921 901 923 901 924 901 925 901 926 901 927 901 928 901 930 901 935 901 936 901 938 901 939 901 940 901 942 901 943 901 945 901 946...
output:
635255
result:
ok single line: '635255'
Test #9:
score: 10
Accepted
time: 72ms
memory: 18216kb
input:
1000 1000 1 19 587 249999 1 1 1 3 1 5 1 7 1 9 1 11 1 13 1 15 1 17 1 19 1 21 1 23 1 25 1 27 1 29 1 31 1 33 1 35 1 37 1 39 1 41 1 43 1 45 1 47 1 49 1 51 1 53 1 55 1 57 1 59 1 61 1 63 1 65 1 67 1 69 1 71 1 73 1 75 1 77 1 79 1 81 1 83 1 85 1 87 1 89 1 91 1 93 1 95 1 97 1 99 1 101 1 103 1 105 1 107 1 109...
output:
750001
result:
ok single line: '750001'
Test #10:
score: 10
Accepted
time: 57ms
memory: 17500kb
input:
1000 1000 111012 587 619 0
output:
111556
result:
ok single line: '111556'
Extra Test:
score: 0
Extra Test Passed