| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 261467 |
2020-08-11T18:32:20 Z |
brcode |
Robots (APIO13_robots) |
C++14 |
|
1500 ms |
154232 KB |
#include <iostream>
#include <bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimization ("Ofast")
using namespace std;
const int MAXN = 510;
int grid[MAXN][MAXN];
int dp[MAXN][MAXN][12][12];
vector<pair<int,int>> res[2];
vector<pair<int,pair<int,int>>> v1;
int n,h,w;
int dx[6] = {0,0,1,0,-1};
int dy[6] = {0,1,0,-1,0};
pair<int,int> visited[MAXN][MAXN][5];
pair<int,int> bot[20];
bool check(int i,int j){
if(i<=0||j<=0||i>w||j>h||grid[i][j] == 0){
return false;
}
return true;
}
pair<int,int> dfs(int i,int j,int dir){
if(visited[i][j][dir]!=make_pair(0,0)){
return visited[i][j][dir];
}
if(grid[i][j]==1){
int nexti = i+dx[dir];
int nextj = j+dy[dir];
if(check(nexti,nextj)){
return visited[i][j][dir] = dfs(nexti,nextj,dir);
}else{
return make_pair(i,j);
}
}
if(grid[i][j]==2){
int newdir = dir;
newdir--;
if(newdir == 0){
newdir = 4;
}
int nexti = i+dx[newdir];
int nextj = j+dy[newdir];
if(check(nexti,nextj)){
return visited[i][j][dir] = dfs(nexti,nextj,newdir);
}else{
return make_pair(i,j);
}
}
if(grid[i][j]==3){
int newdir = dir;
newdir++;
if(newdir == 5){
newdir = 1;
}
int nexti = i+dx[newdir];
int nextj = j+dy[newdir];
if(check(nexti,nextj)){
return visited[i][j][dir] = dfs(nexti,nextj,newdir);
}else{
return make_pair(i,j);
}
}
return make_pair(0,0);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>w>>h;
swap(w,h);
int mx = h*w;
for(int i=1;i<=w;i++){
for(int j=1;j<=h;j++){
char x;
cin>>x;
if(x=='.'){
grid[i][j] = 1;
continue;
}
if(x=='x'){
grid[i][j] = 0;
continue;
}
if(x=='A'){
grid[i][j] = 2;
continue;
}
if(x=='C'){
grid[i][j] = 3;
continue;
}
grid[i][j] = 1;
int y = x-'0';
bot[y] = make_pair(i,j);
}
}
for(int i=1;i<=w;i++){
for(int j=1;j<=h;j++){
for(int x=1;x<=n;x++){
for(int y=1;y<=n;y++){
dp[i][j][x][y] = 1e9;
}
}
}
}
for(int i=1;i<=n;i++){
dp[bot[i].first][bot[i].second][i][i] = 0;
// cout<<i<<" "<<bot[i].first<<" "<<bot[i].second<<endl;
}
for(int i=1;i<=w;i++){
for(int j=1;j<=h;j++){
if(grid[i][j] == 0){
continue;
}
if(visited[i][j][1]== make_pair(0,0)){
dfs(i,j,1);
}
if(visited[i][j][2]== make_pair(0,0)){
dfs(i,j,2);
}
if(visited[i][j][3]== make_pair(0,0)){
dfs(i,j,3);
}
if(visited[i][j][4]== make_pair(0,0)){
dfs(i,j,4);
}
}
}
//cout<<visited[5][5][1].first<<" "<<visited[5][5][1].second<<endl;
for(int len=0;len<=n-1;len++){
for(int x=1;x<=n;x++){
int y = x+len;
if(y>n){
break;
}
for(int i=1;i<=w;i++){
for(int j=1;j<=h;j++){
for(int z=x;z<y;z++){
dp[i][j][x][y] = min(dp[i][j][x][y],dp[i][j][x][z]+dp[i][j][z+1][y]);
}
}
}
res[0].clear();
res[1].clear();
v1.clear();
//int holdmx = 0;
for(int i=1;i<=w;i++){
for(int j=1;j<=h;j++){
if(dp[i][j][x][y]!=1e9){
v1.push_back(make_pair(dp[i][j][x][y],make_pair(i,j)));
}
}
}
sort(v1.begin(),v1.end());
int ptr = 0;
for(int i=0;i<=w*h;i++){
while(ptr<v1.size() && v1[ptr].first==i){
res[i&1].push_back(make_pair(v1[ptr].second.first,v1[ptr].second.second));
ptr++;
}
if(ptr>=v1.size() && res[i&1].size() == 0 && res[1-(i%1)].size() == 0){
break;
}
for(auto tmp:res[i&1]){
int a = tmp.first;
int b = tmp.second;
for(int dir=1;dir<=4;dir++){
int nxti = visited[a][b][dir].first;
int nxtj = visited[a][b][dir].second;
if(nxti == a && nxtj == b){
continue;
}
if(nxti == 0 && nxtj == 0){
continue;
}
if(dp[nxti][nxtj][x][y]>i+1){
dp[nxti][nxtj][x][y] = i+1;
res[(i+1)&1].push_back(make_pair(nxti,nxtj));
}
}
}
res[i&1].clear();
}
}
}
//cout<<visited[1][7][3].first<<" "<<visited[1][7][3].second<<endl;
// cout<<dp[1][7][3][4]<<endl;
int ans = 1e9;
for(int i=1;i<=w;i++){
for(int j=1;j<=h;j++){
ans = min(ans,dp[i][j][1][n]);
}
}
if(ans == 1e9){
ans = -1;
}
cout<<ans<<'\n';
}
Compilation message
robots.cpp:4:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
#pragma GCC optimization ("O3")
robots.cpp:5:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
#pragma GCC optimization ("unroll-loops")
robots.cpp:6:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
#pragma GCC optimization ("Ofast")
robots.cpp: In function 'int main()':
robots.cpp:173:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ptr<v1.size() && v1[ptr].first==i){
~~~^~~~~~~~~~
robots.cpp:178:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(ptr>=v1.size() && res[i&1].size() == 0 && res[1-(i%1)].size() == 0){
~~~^~~~~~~~~~~
robots.cpp:80:9: warning: unused variable 'mx' [-Wunused-variable]
int mx = h*w;
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
512 KB |
Output is correct |
| 5 |
Correct |
1 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
512 KB |
Output is correct |
| 5 |
Correct |
1 ms |
512 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
0 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
0 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
512 KB |
Output is correct |
| 5 |
Correct |
1 ms |
512 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
0 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
0 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
512 KB |
Output is correct |
| 11 |
Correct |
310 ms |
56192 KB |
Output is correct |
| 12 |
Correct |
40 ms |
55416 KB |
Output is correct |
| 13 |
Correct |
147 ms |
57652 KB |
Output is correct |
| 14 |
Correct |
576 ms |
56436 KB |
Output is correct |
| 15 |
Correct |
247 ms |
55864 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
512 KB |
Output is correct |
| 5 |
Correct |
1 ms |
512 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
0 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
0 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
512 KB |
Output is correct |
| 11 |
Correct |
310 ms |
56192 KB |
Output is correct |
| 12 |
Correct |
40 ms |
55416 KB |
Output is correct |
| 13 |
Correct |
147 ms |
57652 KB |
Output is correct |
| 14 |
Correct |
576 ms |
56436 KB |
Output is correct |
| 15 |
Correct |
247 ms |
55864 KB |
Output is correct |
| 16 |
Correct |
591 ms |
154232 KB |
Output is correct |
| 17 |
Execution timed out |
1610 ms |
152304 KB |
Time limit exceeded |
| 18 |
Halted |
0 ms |
0 KB |
- |
