| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1002225 |
2024-06-19T11:07:23 Z |
vjudge1 |
Robots (APIO13_robots) |
C++17 |
|
1 ms |
348 KB |
//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();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
