| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1002208 |
2024-06-19T10:58:48 Z |
vjudge1 |
Robots (APIO13_robots) |
C++17 |
|
537 ms |
10584 KB |
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
#include<deque>
using namespace std;
#define len(x) (int)x.size()
#define all(x) (x).begin() , (x).end()
#define Bekabot ios_base::sync_with_stdio(NULL);cin.tie(0);cout.tie(0);
#define pb push_back
#define pii pair<int , int>
#define F first
#define S second
#define fopen(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
const int N = 1e5 + 78 , M = 1e9 + 7 , inf = 1e18;
int n , w , h;
char a[505][505];
int dp[10][305][305];
int tmp = 1;
int used[305][305];
pii p[10][305][305];
int rev(int x){
if(x == 1)x = 3;
else if(x == 3)x = 2;
else if(x == 2)x = 4;
else if(x == 4)x = 1;
return x;
}
int inv(int x){
if(x == 1)x = 4;
else if(x == 4)x = 2;
else if(x == 2)x = 3;
else if(x == 3)x = 1;
return x;
}
pair<int , pii> calc(int x , int y , int cur){
while(1){
if(a[x][y] == 'A'){
cur = rev(cur);
}
else if(a[x][y] == 'C'){
cur = inv(cur);
}
if(cur == 1){
if(a[x][y + 1] == 'x' or y + 1 > w)break;
y++;
}
else if(cur == 2){
if(a[x][y - 1] == 'x' or y - 1 == 0)break;
y--;
}
else if(cur == 3){
if(a[x - 1][y] == 'x' or x - 1 == 0)break;
x--;
}
else if(cur == 4){
if(a[x + 1][y] == 'x' or x + 1 > h)break;
x++;
}
}
return {x , {y , cur}};
}
void dfs(int x , int y){
used[x][y] = tmp;
//if(tmp == 2)cout << x << ' ' << y << '\n';
queue<pii> q;
q.push({x , y});
while(len(q)){
int v = q.front().F , u = q.front().S;
used[v][u] = 1;
q.pop();
pair<int , pii> cc = calc(v , u , 1);
int x1 = cc.F , y1 = cc.S.F;
if(!used[x1][y1]){
q.push({x1 , y1});
if(dp[tmp][x1][y1] > dp[tmp][v][u] + 1){
dp[tmp][x1][y1] = dp[tmp][v][u] + 1;
p[tmp][x1][y1].F = v , p[tmp][x1][y1].S = u;
}
}
cc = calc(v , u , 2);
x1 = cc.F , y1 = cc.S.F;
if(!used[x1][y1]){
q.push({x1 , y1});
if(dp[tmp][x1][y1] > dp[tmp][v][u] + 1){
dp[tmp][x1][y1] = dp[tmp][v][u] + 1;
p[tmp][x1][y1] = {v , u};
}
}
cc = calc(v , u , 3);
x1 = cc.F , y1 = cc.S.F;
if(!used[x1][y1]){
q.push({x1 , y1});
if(dp[tmp][x1][y1] > dp[tmp][v][u] + 1){
dp[tmp][x1][y1] = dp[tmp][v][u] + 1;
p[tmp][x1][y1] = {v , u};
}
}
cc = calc(v , u , 4);
x1 = cc.F , y1 = cc.S.F;
if(!used[x1][y1]){
q.push({x1 , y1});
if(dp[tmp][x1][y1] > dp[tmp][v][u] + 1){
dp[tmp][x1][y1] = dp[tmp][v][u] + 1;
p[tmp][x1][y1] = {v , u};
}
}
}
}
//1 >
//2 <
//3 ^
//4 v
bool cmp(pii x , pii y){
return a[x.F][x.S] < a[y.F][y.S];
}
void skibidi_dop_dop_dop_yes_yes(){
cin >> n >> w >> h;
vector<pii> v;
for(int i = 1 ; i <= h ; i++){
for(int j = 1 ; j <= w ; j++){
cin >> a[i][j];
dp[1][i][j] = dp[2][i][j] = dp[3][i][j] = dp[4][i][j] = dp[5][i][j] = dp[6][i][j] = dp[7][i][j] = dp[8][i][j] = dp[9][i][j] = inf;
if(a[i][j] >= '1' and a[i][j] <= '9')v.pb({i , j});
}
}
sort(all(v) , cmp);
for(auto it : v){
dp[tmp][it.F][it.S] = 0;
dfs(it.F , it.S);
tmp++;
for(int i = 1 ; i <= h ; i++)for(int j = 1 ; j <= w ; j++)used[i][j] = 0;
//break;
}
int mn = inf;
if(n == 1){
cout << 0;
return;
}
for(int i = 1 ; i <= h ; i++){
for(int j = 1 ; j <= w ; j++){
if(i >= 150)break;
int sum = 0;
set<pii> st;
bool ok = 1;
for(int k = 1 ; k < tmp ; k++){
sum += dp[k][i][j];
if(dp[k][i][j] >= inf){
ok = 0;
break;
}
int x = i , y = j;
int aa = 200;
//cout << x << ' ' << y << '\n';
//cout << v[k - 1].F << ' ' << v[k - 1].S << '\n';
// if(i == 1 and j == 3 and k == 1)cout << x << ' ' << y << '\n';
while(x != v[k - 1].F or y != v[k - 1].S){
aa--;
if(!aa)break;
auto pp = p[k][x][y];
x = pp.F , y = pp.S;
if(!x or !y)break;
//if(i == 1 and j == 1 and k == 3)cout << x << ' ' << y << '\n';
//cout << x << ' ' << y << '\n';
st.insert({x , y});
}
}
// cout << dp[2][i][j] << ' ';
// cout << dp[1][i][j] << ' ';
//if(len(st) == 0 and ok)cout << i << ' ' << j << '\n';
// if(i == 1 and j == 1 and ok){
// cout << dp[4][i][j] << '\n';
// for(auto it : st)cout << it.F << ' ' << it.S << '\n';
// }
if(ok)mn = min(mn , len(st));
}
//cout << '\n';
}
// cout << p[3][1][1].S;
if(mn < inf)cout << mn;
else cout << -1;
}
signed main(){
int t = 1;
Bekabot
while(t--)skibidi_dop_dop_dop_yes_yes();
}
Compilation message
robots.cpp:21:46: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
21 | const int N = 1e5 + 78 , M = 1e9 + 7 , inf = 1e18;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
600 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 |
604 KB |
Output is correct |
| 5 |
Correct |
0 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
600 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 |
604 KB |
Output is correct |
| 5 |
Correct |
0 ms |
604 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
760 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
600 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 |
604 KB |
Output is correct |
| 5 |
Correct |
0 ms |
604 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
760 KB |
Output is correct |
| 11 |
Incorrect |
537 ms |
10584 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
600 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 |
604 KB |
Output is correct |
| 5 |
Correct |
0 ms |
604 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
760 KB |
Output is correct |
| 11 |
Incorrect |
537 ms |
10584 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
