QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#640827#6259. Gluttonous Goopchanuuu#RE 1ms3868kbC++171.6kb2024-10-14 16:19:162024-10-14 16:19:20

Judging History

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

  • [2024-10-14 16:19:20]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3868kb
  • [2024-10-14 16:19:16]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

char mp[202][202];
const int dx[] = {-1,-1,-1,0,0,1,1,1}, dy[] = {-1,0,1,-1,1,-1,0,1};

struct st{
    int x, y, d;
};

int main(){
    cin.tie(nullptr)->sync_with_stdio(0);
    int n,m,k, c = 0;
    cin >> n >> m >> k;
    queue<st> q;
    memset(mp, '.', sizeof mp);
    for (int i = 81; i <= n+80; i++){
        for (int j = 81; j <= m+80; j++){
            cin >> mp[i][j];
            if (mp[i][j] == '#'){
                c++;
                q.push({j,i,0});
            }
        }
    }
    int bef = 0, aa = c;
    vector<int> diff;
    while (q.size() and q.front().d < 50){
        int x,y,d;
        x = q.front().x;
        y = q.front().y;
        d = q.front().d;
        q.pop();
        if (d != bef){
            diff.push_back(c - aa);
            // cout << aa << ' ' << c << ' ' << diff.back() << endl;
            bef = d;
            aa = c;
        }
        if (d == k){
            cout << c;
            return 0;
        }
        for (int i = 0; i < 8; i++){
            int nx = x + dx[i], ny = y + dy[i];
            if (mp[ny][nx] != '#'){
                mp[ny][nx] = '#';
                c++;
                q.push({nx, ny, d+1});
            }
        }
    }
    // if (k == 50) {
    //     cout << c;
    //     return 0;
    // }
    ll cha = diff.back() - diff[diff.size()-2];
    // cout << c - aa << ' ' << cha <<endl;
    // assert(c - aa -  == cha)?;
    ll ccc = k - 50;
    cout << c + (c-aa)*ccc + (ccc+1)*ccc/2 * cha;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3564kb

input:

5 5 3
.....
.###.
.#.#.
.###.
.....

output:

81

result:

ok single line: '81'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3864kb

input:

3 3 1
#..
.#.
..#

output:

19

result:

ok single line: '19'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3564kb

input:

4 6 3
..##..
.#..#.
.#..#.
..##..

output:

96

result:

ok single line: '96'

Test #4:

score: 0
Accepted
time: 1ms
memory: 3828kb

input:

1 1 1000000
#

output:

4000004000001

result:

ok single line: '4000004000001'

Test #5:

score: 0
Accepted
time: 1ms
memory: 3860kb

input:

2 2 91011
.#
.#

output:

33132554552

result:

ok single line: '33132554552'

Test #6:

score: 0
Accepted
time: 1ms
memory: 3580kb

input:

20 20 1000000
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
#############...

output:

4000080000400

result:

ok single line: '4000080000400'

Test #7:

score: 0
Accepted
time: 1ms
memory: 3868kb

input:

20 20 630238
....................
....................
....................
....................
....................
....................
....................
....................
#...................
....................
....................
....................
....................
.................

output:

1588840081630

result:

ok single line: '1588840081630'

Test #8:

score: 0
Accepted
time: 1ms
memory: 3640kb

input:

20 20 630238
#...................
.#..................
..#.................
...#................
....#...............
.....#..............
......#.............
.......#............
........#...........
.........#..........
..........#.........
...........#........
............#.......
.............#...

output:

1588850165636

result:

ok single line: '1588850165636'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3796kb

input:

20 20 1000000
.........##.........
........####........
.......######.......
......########......
.....##########.....
....############....
...##############...
..################..
.##################.
####################
####################
.##################.
..################..
...##########...

output:

4000080000220

result:

ok single line: '4000080000220'

Test #10:

score: -100
Runtime Error

input:

5 5 1000000
.....
.....
.....
.....
.....

output:


result: