Submission #1002225

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002225		vjudge1	Robots (APIO13_robots)	C++17	10 / 100	1 ms	348 KiB

robots

//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)
#define ins insert
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[1001][1001];
map <pii , vector <pii>> g;
map <pii , int> used , dist1 , dist;
map <tpii , int> was;
vector <pii> c;
bool ok = 0;
void go(int i , int j , int tp){
	// cout << i << ' ' << j << ' ' << tp<< '\n';
	if(was[{{i , j} , tp}]){
		c.clear();
		ok = 1;
		return;
	} 
	was[{{i , j} , tp}]++;
	if(tp == 1){
		for(int k = i - 1 ; k >= 1 ; k--){
			if(a[k][j] == 'x'){
				c.pb({k + 1 , j});
				// cout << i << ' ' << j << ' ' << k + 1 << ' ' << j << '\n';
				return;
			}
			if(a[k][j] == 'A'){
				go(k , j , 3);
				// cout << "WAS\n";
				return;
			}
			if(a[k][j] == 'C'){
				ok = 1;
				go(k , j , 4);
				return; 
			}
		}
		c.pb({1 , j});
		// cout << i << ' ' << j << ' ' /<< 1 << ' ' << j << '\n';
		return;
	}
	if(tp == 2){
		for(int k = i + 1 ; k <= w ; k++){
			if(a[k][j] == 'x'){
				c.pb({k - 1 , j});
				return;
			}
			if(a[k][j] == 'A'){
				// cout << i << ' ' << j << ' ' << k << ' ' << tp << '\n';
				go(k , j , 4);
				return;
			}
			if(a[k][j] == 'C'){
				go(k , j , 3);
				return;
			}
		}
		c.pb({w , j});
		return;
	}
	if(tp == 3){
		for(int k = j - 1 ; k >= 1 ; k--){
			if(a[i][k] == 'x'){
				c.pb({i , k + 1});
				return;
			}
			if(a[i][k] == 'A'){
				go(k , j , 2);
				return;
			}
			if(a[i][k] == 'C'){
				go(k , j , 1);
				return; 
			}
		}
		c.pb({i , 1});
		return;
	}
	if(tp == 4){
		for(int k = j + 1 ; k <= h ; k++){
			if(a[i][k] == 'x'){
				c.pb({i , k - 1});
				return;
			}
			if(a[i][k] == 'A'){
				// cout << i << ' ' << j << ' ' << k << ' ' << tp << '\n';
				 go(k , j , 1);
				return;
			}
			if(a[i][k] == 'C'){
				 go(k , j , 2);
				return;
			}
		}
		c.pb({i , h});
		return;
	}
}
void Tima(){
	cin >> n >> w >> h;
	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;
			go(i , j , 1);
			for(auto it : c){
				if(it.F == i && it.S == j) continue;
				g[{i , j}].pb(it);
				// cout << i << ' ' << j << ' ' << it.F << ' ' << it.S << '\n';
			}
			c.clear();
			was.clear();
			go(i , j , 2);
			for(auto it : c){
				if(it.F == i && it.S == j) continue;
				g[{i , j}].pb(it);
				// cout << i << ' ' << j << ' ' << it.F << ' ' << it.S << '\n';
			}
			c.clear();
			was.clear();
			go(i , j , 3);
			for(auto it : c){
				if(it.F == i && it.S == j) continue;
				g[{i , j}].pb(it);
				// cout << i << ' ' << j << ' ' << it.F << ' ' << it.S << '\n';
			}
			c.clear();
			was.clear();
			go(i , j , 4);
			for(auto it : c){
				if(it.F == i && it.S == j) continue;
				g[{i , j}].pb(it);
				// cout << i << ' ' << j << ' ' << it.F << ' ' << it.S << '\n';
			}
			c.clear();
			was.clear();
		}
	}
	// for(auto it : g[b]){
		// cout << it.F << ' ' << it.S << '\n';
	// }
	deque <pii> q;
	for(int i = 1 ; i <= w ; i++){
		for(int j = 1 ; j <= h ; j++){
			dist[{i , j}] = INF;
			dist1[{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]);
	// cout << ans << '\n';
	for(int i = 1 ; i <= w ; i++){
		for(int j = 1 ; j <= h ; j++){
			used[{i , j}] = 0;
		}
	}
	swap(b , e);
	q.pb(b);
	used[b] = 1;
	dist1[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';
				dist1[to] = min(dist1[v] + 1 , dist1[to]);
				used[to] = 1; 
				q.pb(to);
			}
		}
	}
	ans = min(ans , dist1[e]);
	// cout << ans << '\n';
	for(int i = 1 ; i <= w ; i++){
		for(int j = 1 ; j <= h ; j++){
			if(a[i][j] == 'x') continue;
			if(a[i - 1][j] == '.' && a[i + 1][j] == '.' && a[i][j - 1] == '.' && a[i][j + 1] == '.') continue;
			ans = min(ans , dist1[{i , j}] + dist[{i , j}]);
		}
	}
	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();
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40