QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#847842 | #8236. Snake Move | Red0 | TL | 0ms | 3844kb | C++20 | 5.3kb | 2025-01-08 11:52:02 | 2025-01-08 11:52:10 |
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, tx = 0, ty = 0;
repe(i, 1, k) {
int x, y;
cin >> x >> y;
if (i == 1) hx = x, hy = y;
else if (i == k) tx = x, ty = 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};
int mtime = n+m+k;
vvc<pii> process(mtime+1);
process[0].pb({hx, hy});
repe(t, 0, mtime) {
for (auto &[cx, cy] : process[t]) {
if (dist[cx][cy] < t) continue;
dist[cx][cy] = t;
//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 = org_snake[tx][ty]-org_snake[nx][ny]-t;
if (steps_needed > 0) {
process[t+1+steps_needed].push_back({nx, ny});
} else {
process[t+1].push_back({nx, ny});
}
} else {
process[t+1].push_back({nx, ny});
}
}
}
}
__int128_t ans = 0;
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]);
}
}
}
__int128_t mod = 2;
repe(i, 1, 63) mod *= 2;
ans %= mod;
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: 0ms
memory: 3844kb
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: 3648kb
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: 3616kb
input:
5 5 3 1 2 1 1 2 1 ..... .###. .#.#. .###. .....
output:
407
result:
ok single line: '407'
Test #4:
score: -100
Time Limit Exceeded
input:
3000 2900 1 1882 526 ........................................................................................................#................................................................................................................................................................#................