QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#847915#8236. Snake MoveRed0WA 896ms83084kbC++206.8kb2025-01-08 13:15:302025-01-08 13:15:30

Judging History

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

  • [2025-01-08 13:15:30]
  • 评测
  • 测评结果:WA
  • 用时:896ms
  • 内存:83084kb
  • [2025-01-08 13:15:30]
  • 提交

answer

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

//Debug Template:
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

//#define int long long

//Random Number Generator:
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        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 = rng();
        return splitmix64(x+FIXED_RANDOM);
    }
};

//Custom Data Structures:
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using safe_set = unordered_set<T, custom_hash>;
template<typename T, typename V> using safe_map = unordered_map<T, V, custom_hash>;
template<typename T> using vc = vector<T>; template<typename T> using vvc = vc<vc<T>>; template<typename T> using vvvc = vc<vvc<T>>;
template<typename T, int V> using ar = array<T, V>;
template<typename T, typename V> using pr = pair<T, V>;
using vi = vc<int>; using vvi = vvc<int>; using vvvi = vvvc<int>;
using pii = pr<int, int>;

//Macros:
#define repl(i, a, b) for(int i = a; i < b; ++i)
#define repe(i, a, b) for(int i = a; i <= b; ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pow(b, p) (int)pow(b, p)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fir first
#define sec second
#define lsb(x) (int)__builtin_ctzll(x)
#define msb(x) (int)(63-__builtin_clzll(x))
#define yes cout << "YES\n"
#define no cout << "NO\n"

#define readall(x) trav(it, x) cin >> it;
#define printall(x) trav(it, x) cout << it << " ";
#define getmin(x) *min_element(all(x))
#define getmax(x) *max_element(all(x))

//c Problem Info:
const int MAX_N = 200005;
const int MAX_M = 200005;
const int INF = 1000000000;
const int MOD = pow(2, 64);

void solve() {
    int n, m, k;
    cin >> n >> m >> k;

    //represents if some square is a snake and also represents distance+1 from head;
    vvi org_snake(n+1, vi(m+1, 0));
    int hx = 0, hy = 0;
    repe(i, 1, k) {
        int x, y;
        cin >> x >> y;

        if (i == 1) hx = x, hy = y;
        org_snake[x][y] = i;
    }

    vvc<char> grid(n+1, vc<char>(m+1));
    repe(i, 1, n) {
        repe(j, 1, m) cin >> grid[i][j];
    }

    vvi dist(n+1, vi(m+1, INF));
    int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
    priority_queue<ar<int, 4>, vc<ar<int, 4>>, greater<>> pq;
    //pre-initialize the head of the snake;
    dist[hx][hy] = 0;
    pq.push({0, 0, hx, hy});
    while (!pq.empty()) {
        auto [csteps, hasremoved, cx, cy] = pq.top();
        pq.pop();
        //transition to next locations, up, down, left, right;
        repl(i, 0, 4) {
            int nx = cx+dx[i], ny = cy+dy[i];

            if (nx < 1 || nx > n || ny < 1 || ny > m || dist[nx][ny] != INF || grid[nx][ny] == '#') continue;
            if (org_snake[nx][ny] != 0) {
                //check to see if the head will hit the body;
                int steps_needed = k-org_snake[nx][ny]-csteps;
                if (steps_needed > 0) {
                    //if already removed, then we don't need to worry about this;
                    if (hasremoved) {
                        dist[nx][ny] = csteps+1;
                        pq.push({csteps+1, 1, nx, ny});
                    } else {
                        //we will wait the necessary # of steps;
                        dist[nx][ny] = csteps+1+steps_needed;
                        pq.push({csteps+1+steps_needed, 1, nx, ny});
                    }
                } else {
                    dist[nx][ny] = csteps+1;
                    pq.push({csteps+1, hasremoved, nx, ny});
                }
            } else {
                dist[nx][ny] = csteps+1;
                pq.push({csteps+1, hasremoved, nx, ny});
            }
        }
    }

    /*int mtime = n+m+k;
    vvc<pii> process(mtime+1);
    process[0].pb({hx, hy});
    dist[hx][hy] = 0;
    repe(t, 0, mtime) {
        for (auto &[cx, cy] : process[t]) {
            if (dist[cx][cy] < t) continue;
            //transition to next locations, up, down, left, right;
            repl(i, 0, 4) {
                int nx = cx+dx[i], ny = cy+dy[i];
                if (nx < 1 || nx > n || ny < 1 || ny > m || dist[nx][ny] != INF || grid[nx][ny] == '#') continue;
                if (org_snake[nx][ny] != 0) {
                    //check to see if the head will hit the body;
                    int steps_needed = k-org_snake[nx][ny]-t;
                    if (steps_needed > 0) {
                        dist[nx][ny] = t+1+steps_needed;
                        process[t+1+steps_needed].pb({nx, ny});
                    } else {
                        dist[nx][ny] = t+1;
                        process[t+1].pb({nx, ny});
                    }
                } else {
                    dist[nx][ny] = t+1;
                    process[t+1].pb({nx, ny});
                }
            }
        }
    }*/

    __int128_t ans = 0, mod = 2;
    repe(i, 1, 63) mod *= 2;
    repe(i, 1, n) {
        repe(j, 1, m) {
            if (dist[i][j] != INF) {
                ans = (ans+__int128_t(dist[i][j])*__int128_t(dist[i][j])%mod)%mod;
            }
        }
    }

    //debug(dist);
    cout << uint64_t(ans) << "\n";
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    //cin >> t;

    while(t--) {
        solve();
    }

    return 0;
}

详细

Test #1:

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

input:

4 5 5
3 5
3 4
3 3
3 2
4 2
.....
.....
.....
.....

output:

293

result:

ok single line: '293'

Test #2:

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

input:

2 2 4
1 1
1 2
2 2
2 1
..
..

output:

14

result:

ok single line: '14'

Test #3:

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

input:

5 5 3
1 2
1 1
2 1
.....
.###.
.#.#.
.###.
.....

output:

407

result:

ok single line: '407'

Test #4:

score: 0
Accepted
time: 828ms
memory: 80360kb

input:

3000 2900 1
1882 526
........................................................................................................#................................................................................................................................................................#................

output:

35141960580077

result:

ok single line: '35141960580077'

Test #5:

score: 0
Accepted
time: 874ms
memory: 80420kb

input:

2900 3000 1
1333 1773
.....#....#......#.#..#...#.....#.#.#.#....#...###.#..#.....##....####..#......#.......######.#........#..#......#...###.#.#..#.....#.#........##..#..#.#..#.###.#.#...#..#.##..#...#....#..#.##..#......#.######............#.#...#......#......#..#.#.#.#...#...#..##........#.###.....

output:

17464052497724

result:

ok single line: '17464052497724'

Test #6:

score: 0
Accepted
time: 65ms
memory: 82724kb

input:

3000 3000 1
2755 225
##..#.##.....####..#...###.#.##.#.##.#......###.#####..#..####....#.#.####..##..##.#...#...##..#.#.##..#....##.#...#.....##.#...##.##.##..##..#######.####.####......##.##.#....#..#.....#..##.#.#...#.####..##.#..#...###..###.#.#...##.#.....###.####......##...#...#....#.#...#.#.#....

output:

255915

result:

ok single line: '255915'

Test #7:

score: 0
Accepted
time: 75ms
memory: 80068kb

input:

3000 2900 1
878 738
#.##.##..##.#.#.###.#...###.####.#.###.####.##.#.#####.#.####..#.#.###.###..####.####...###..####.########..##..#####.#....#####.#.#########..#.###.##.##.#####.#####.#.##..###..##.#####.#.############..##.###.##.##..########.#.###..###...######.####...#######.###.###..####.######...

output:

1

result:

ok single line: '1'

Test #8:

score: 0
Accepted
time: 829ms
memory: 80352kb

input:

2900 3000 10
2883 1758
2883 1759
2883 1760
2883 1761
2883 1762
2884 1762
2884 1763
2883 1763
2882 1763
2882 1764
........................................................#............................#........................................................................................................

output:

49803365625286

result:

ok single line: '49803365625286'

Test #9:

score: 0
Accepted
time: 896ms
memory: 83004kb

input:

3000 3000 10
2015 1932
2015 1931
2015 1930
2015 1929
2016 1929
2017 1929
2018 1929
2018 1928
2018 1927
2017 1927
#...#...#..#.........#.......#####....#...###..#..###..###....##.....#..#..#...#.....##...##.#..#..##.###.........##.....#....#..##.##.#.#.##.#.#.#.....#....##.##.#..##....#....#...#.#......

output:

22509095749285

result:

ok single line: '22509095749285'

Test #10:

score: 0
Accepted
time: 79ms
memory: 79980kb

input:

3000 2900 10
326 1781
325 1781
325 1782
325 1783
325 1784
324 1784
324 1783
323 1783
323 1782
324 1782
##.#....#.###.######..#.#.....##.#.##..####.####.##..#..#.###.#####....##.#.##.#..###..##.###.##.#####.###..##.#..##..##.#..##.#.#.##...##..#.##.##........#..#..###.##.###.####.#..########.##.....#...

output:

40571

result:

ok single line: '40571'

Test #11:

score: 0
Accepted
time: 71ms
memory: 80088kb

input:

2900 3000 10
2447 135
2447 136
2447 137
2447 138
2447 139
2447 140
2448 140
2448 139
2449 139
2449 138
.#.##.##..#.###########.#####.###....#####.########..##..#.####.##.##.####.####..#.#####.##.#.#.###.##.#.##.####..##.#.####..###..###...##...##.#####.#####.#...#####.####..##.##.#.#..#..####.##..##...

output:

2705

result:

ok single line: '2705'

Test #12:

score: -100
Wrong Answer
time: 855ms
memory: 83084kb

input:

3000 3000 100
2573 1917
2572 1917
2572 1916
2573 1916
2574 1916
2574 1915
2573 1915
2572 1915
2571 1915
2571 1914
2570 1914
2570 1915
2569 1915
2569 1916
2568 1916
2568 1917
2569 1917
2570 1917
2570 1916
2571 1916
2571 1917
2571 1918
2570 1918
2569 1918
2569 1919
2570 1919
2571 1919
2571 1920
2572 1...

output:

41693682059381

result:

wrong answer 1st lines differ - expected: '41693682087973', found: '41693682059381'