QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#847915 | #8236. Snake Move | Red0 | WA | 896ms | 83084kb | C++20 | 6.8kb | 2025-01-08 13:15:30 | 2025-01-08 13:15:30 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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'