Submission #1048765

#TimeUsernameProblemLanguageResultExecution timeMemory
1048765adiyerRobots (APIO13_robots)C++17
0 / 100
10 ms72280 KiB
// #pragma optimize ("g",on) // #pragma GCC optimize("inline") // #pragma GCC optimize ("Ofast") // #pragma GCC optimize ("unroll-loops") // #pragma GCC optimize ("03") // #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,avx2,mmx,fma,avx,tune=native") #include <bits/stdc++.h> #define file(s) freopen(s".in", "r", stdin); freopen(s".out", "w", stdout); #define adiyer(); ios_base::sync_with_stdio(0); cin.tie(0); #define bitcount(n) __builtin_popcountll(n) #define puts(x) (x ? "YES\n" : "NO\n"); #define ent (i == n ? '\n' : ' ') #define all(x) x.begin(), x.end() #define md ((l + r) >> 1) #define rv(v) ((v << 1) | 1) #define lv(v) (v << 1) #define rs(v) rv(v), md + 1, r #define ls(v) lv(v), l, md #define len(s) (int) s.size() #define pb push_back #define S second #define F first // #define int long long using namespace std; typedef long long ll; typedef long double ld; typedef vector < ll > vll; typedef pair < ll, ll > pll; typedef vector < pair < ll, ll > > vpll; const int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1}; const int dy[8] = {0, 1, 0, -1, -1, 1, -1, 1}; const int N = 5e2 + 23; const int K = 2e5; const int mod = 998244353; const ll inf = 1e9 + 10; //mt19937 rnd(07062006); ll k, n, m, res, cur, cnt; ll d[10][N][N], ans[10][10][N][N]; pll was[N][N][2][2][2][2]; char a[N][N]; bool good(ll x, ll y){ return x >= 1 && y >= 1 && x <= n && y <= m && a[x][y] != 'x'; } void move(ll &x, ll &y, ll d1, ll d2, ll d3, ll d4){ ll X = x, Y = y; vector < vll > v; v.pb({x, y, d1, d2, d3, d4}); while(1){ // cout << x << ' ' << y << '\n'; if(a[x][y] == 'C'){ if(d1) d1 = 0, d2 = 1; else if(d2) d2 = 0, d3 = 1; else if(d3) d3 = 0, d4 = 1; else d4 = 0, d1 = 1; } if(a[x][y] == 'A'){ if(d1) d1 = 0, d4 = 1; else if(d2) d2 = 0, d1 = 1; else if(d3) d3 = 0, d2 = 1; else d4 = 0, d3 = 1; } if(d1) y++; else if(d2) x++; else if(d3) y--; else x--; if(!good(x, y)) break; v.pb({x, y, d1, d2, d3, d4}); } x = v[len(v) - 1][0], y = v[len(v) - 1][1]; if(!was[v[len(v) - 1][0]][v[len(v) - 1][1]][v[len(v) - 1][2]][v[len(v) - 1][3]][v[len(v) - 1][4]][v[len(v) - 1][5]].F){ was[v[len(v) - 1][0]][v[len(v) - 1][1]][v[len(v) - 1][2]][v[len(v) - 1][3]][v[len(v) - 1][4]][v[len(v) - 1][5]] = {x, y}; } for(auto it : v) was[it[0]][it[1]][it[2]][it[3]][it[4]][it[5]] = was[v[len(v) - 1][0]][v[len(v) - 1][1]][v[len(v) - 1][2]][v[len(v) - 1][3]][v[len(v) - 1][4]][v[len(v) - 1][5]] = {x, y}; // for(auto it : v) cout << it[0] << ' ' << it[1] << '\n'; // cout << x << ' ' << y << ' ' << d[1][x][y] << '\n'; } void bfs(pll s, ll id){ ll x, y; queue < pll > q; for(ll i = 1; i <= n; i++) for(ll j = 1; j <= m; j++) d[id][i][j] = inf; for(ll i = 1; i <= n; i++) for(ll j = 1; j <= m; j++) for(ll d1 = 0; d1 <= 1; d1++) for(ll d2 = 0; d2 <= 1; d2++) for(ll d3 = 0; d3 <= 1; d3++) for(ll d4 = 0; d4 <= 1; d4++) was[i][j][d1][d2][d3][d4] = {0, 0}; q.push(s), d[id][s.F][s.S] = 0; while(len(q)){ auto [X, Y] = q.front(); q.pop(); x = X, y = Y, move(x, y, 0, 0, 0, 1); if(good(x, y) && d[id][X][Y] + 1 < d[id][x][y]){ d[id][x][y] = d[id][X][Y] + 1; q.push({x, y}); } x = X, y = Y, move(x, y, 0, 0, 1, 0); if(good(x, y) && d[id][X][Y] + 1 < d[id][x][y]){ d[id][x][y] = d[id][X][Y] + 1; q.push({x, y}); } x = X, y = Y, move(x, y, 0, 1, 0, 0); if(good(x, y) && d[id][X][Y] + 1 < d[id][x][y]){ d[id][x][y] = d[id][X][Y] + 1; q.push({x, y}); } x = X, y = Y, move(x, y, 1, 0, 0, 0); if(good(x, y) && d[id][X][Y] + 1 < d[id][x][y]){ d[id][x][y] = d[id][X][Y] + 1; q.push({x, y}); } } // exit(0); } vll v; vpll pos[N * N * 10]; vector < vll > vp = {{0, 0, 0, 1}, {0, 0, 1, 0}, {0, 1, 0, 0}, {1, 0, 0, 0}}; void output(){ cin >> k >> m >> n, res = inf; for(ll i = 1; i <= n; i++) for(ll j = 1; j <= m; j++) cin >> a[i][j]; for(ll i = 1; i <= n; i++) for(ll j = 1; j <= m; j++) if('1' <= a[i][j] && a[i][j] <= '9') bfs({i, j}, a[i][j] - '0'); queue < pll > q; for(ll sz = 1; sz <= k; sz++){ for(ll l = 1; l + sz - 1 <= n; l++){ ll r = l + sz - 1; pair < ll, pll > mn = {inf, {inf, inf}}; for(ll i = 1; i <= n; i++){ for(ll j = 1; j <= m; j++){ if(sz == 1){ ans[l][r][i][j] = d[l][i][j]; continue; } ans[l][r][i][j] = inf; for(ll id = l; id < r; id++){ ans[l][r][i][j] = min(ans[l][r][i][j], ans[l][id][i][j] + ans[id + 1][r][i][j]); } if(ans[l][r][i][j] < inf){ v.pb(ans[l][r][i][j]); pos[ans[l][r][i][j]].pb({i, j}); mn = min(mn, {ans[l][r][i][j], {i, j}}); } } } if(mn.F == inf) continue; for(auto x : pos[mn.F]) q.push(x); pos[mn.F].clear(); while(len(q)){ auto [x, y] = q.front(); q.pop(); ll cst = ans[l][r][x][y]; if(pos[cst + 1].empty()){ for(auto it : pos[cst + 1]){ if(ans[l][r][it.F][it.S] <= cst) continue; q.push(it); } } for(auto it : vp){ auto nxt = was[x][y][it[0]][it[1]][it[2]][it[3]]; if(ans[l][r][nxt.F][nxt.S] <= cst) continue; ans[l][r][nxt.F][nxt.S] = cst + 1; q.push(nxt); } } for(auto it : v) pos[it].clear(); v.clear(); } } for(ll i = 1; i <= n; i++) for(ll j = 1; j <= m; j++) res = min(res, ans[1][k][i][j]); if(res == inf) res = -1; cout << res; } const bool cases = 0; signed main(){ // file("disrupt"); adiyer(); int tt = 1; if(cases) cin >> tt; for(int i = 1; i <= tt; i++){ output(); } }

Compilation message (stderr)

robots.cpp: In function 'void move(ll&, ll&, ll, ll, ll, ll)':
robots.cpp:58:5: warning: unused variable 'X' [-Wunused-variable]
   58 |  ll X = x, Y = y;
      |     ^
robots.cpp:58:12: warning: unused variable 'Y' [-Wunused-variable]
   58 |  ll X = x, Y = y;
      |            ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...