QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#93982#5818. MacaronHaccerKat100 ✓72ms18216kbC++208.0kb2023-04-04 13:39:102023-04-04 13:39:12

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-04 13:39:12]
  • 评测
  • 测评结果:100
  • 用时:72ms
  • 内存:18216kb
  • [2023-04-04 13:39:10]
  • 提交

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