Submission #1001831

#TimeUsernameProblemLanguageResultExecution timeMemory
1001831vjudge1Robots (APIO13_robots)C++17
0 / 100
1 ms348 KiB
//order_of_key(k): Number of items strictly smaller than k . //find_by_order(k): K-th element in a set (counting from zero). //#pragma GCC optimize("O3,unroll-loops") //#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") /*TAAK ZDES NADO RECURSIU PISAT*/ //MADE BY CHATGPT ANAU MNAU I CHUT CHUT TIMA #include "bits/stdc++.h" #include <ext/pb_ds/assoc_container.hpp> #define ll long long #define pb push_back #define pf push_front #define ppb pop_back #define int long long #define F first #define S second #define all(x) (x).begin(), (x).end() #define len(x) (int)x.size() #define nep next_permutation #define itn int #define reutrn return #define reutnr return #define pii pair<int,int> #define tpii pair<pair<int,int>,int> #define fpii pair<pair<int,int>,pair<int,int>> #define sigma signed #define cni cin #define cotu cout #define cotninue continue #define breka break #define al(x , y , z) x + z , x + y + z #define bits(x) __builtin_popcount(x) using namespace std; using namespace __gnu_pbds; const int N = 3e5 + 5; int mod = 1e9 + 7; const int modik = 998244353; const int INF = 1e18; int n,h,w; char a[501][501]; map <pii , vector <pii>> g; map <pii , int> used , dist; void Tima(){ cin >> n >> h >> w; pii b , e; for(int i = 1 ; i <= w ; i++){ for(int j = 1 ; j <= h ; j++){ cin >> a[i][j]; if(a[i][j] == '1'){ b = {i , j}; } if(a[i][j] == '2'){ e = {i , j}; } } } for(int i = 1 ; i <= w ; i++){ for(int j = 1 ; j <= h ; j++){ if(a[i][j] == 'x') continue; bool ok = 0; for(int k = i - 1 ; k >= 1 ; k--){ if(a[k][j] == 'x'){ ok = 1; g[{i , j}].pb({k + 1 , j}); // g[{k + 1 , j}].pb({i , j}); break; } if(a[k][j] == '1' || a[k][j] == '2'){ g[{i , j}].pb({k , j}); } } if(!ok){ g[{i , j}].pb({1 , j}); // g[{1 , j}].pb({i , j}); } ok = 0; for(int k = i + 1 ; k <= w ; k++){ if(a[k][j] == 'x'){ ok = 1; g[{i , j}].pb({k - 1 , j}); // g[{k - 1 , j}].pb({i , j}); break; } if(a[k][j] == '1' || a[k][j] == '2'){ g[{i , j}].pb({k , j}); } } if(!ok){ g[{i , j}].pb({w , j}); // g[{w , j}].pb({i , j}); } ok = 0; for(int k = j - 1 ; k >= 1 ; k--){ if(a[i][k] == 'x'){ ok = 1; g[{i , j}].pb({i , k + 1}); // g[{i , k + 1}].pb({i , j}); break; } if(a[i][k] == '1' || a[i][k] == '2'){ g[{i , j}].pb({i , k}); } } if(!ok){ g[{i , j}].pb({i , 1}); // g[{i , 1}].pb({i , j}); } ok = 0; for(int k = j + 1 ; k <= h ; k++){ if(a[i][k] == 'x'){ ok = 1; g[{i , j}].pb({i , k - 1}); // g[{i , k - 1}].pb({i , j}); break; } if(a[i][k] == '1' || a[i][k] == '2'){ g[{i , j}].pb({i , k}); } } if(!ok){ g[{i , j}].pb({i , h}); // g[{i , h].pb({i , j}); } } } deque <pii> q; for(int i = 1 ; i <= w ; i++){ for(int j = 1 ; j <= h ; j++){ dist[{i , j}] = INF; } } q.pb(b); used[b] = 1; dist[b] = 0; int ans = INF; while(q.size()){ pii v = q.front(); q.pop_front(); for(auto to : g[v]){ if(!used[to]){ dist[to] = min(dist[v] + 1 , dist[to]); // cout << v.F << ' ' << v.S << ' ' << to.F << ' ' << to.S << ' ' << a[v.F][v.S] << ' ' << a[to.F][to.S] << ' ' << dist[v] << ' ' << dist[to] << '\n'; used[to] = 1; q.pb(to); } } } ans = min(ans , dist[e]); for(int i = 1 ; i <= w ; i++){ for(int j = 1 ; j <= h ; j++){ dist[{i , j}] = INF; used[{i , j}] = 0; } } swap(b , e); q.pb(b); used[b] = 1; dist[b] = 0; // ans = INF; while(q.size()){ pii v = q.front(); q.pop_front(); for(auto to : g[v]){ if(!used[to]){ // cout << v.F << ' ' << v.S << ' ' << to.F << ' ' << to.S << ' ' << a[v.F][v.S] << ' ' << a[to.F][to.S] << '\n'; dist[to] = min(dist[v] + 1 , dist[to]); used[to] = 1; q.pb(to); } } } ans = min(ans , dist[e]); cout << (ans == INF ? -1 : ans); } //It is not important to be better than someone else, but to be better than you were yesterday... //Push yourself, because no one else is going to do it for you.. sigma main(){ //freopen("txt.in","r",stdin); //freopen("txt.out","w",stdout); ios_base::sync_with_stdio(0); cin.tie(0); srand(time(0)); int TT = 1; // cin >> TT; for(int i = 1 ; i <= TT ; i++){ //cout << "Case " << i << ": "; Tima(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...