oj.uz

Submission #246930

# Submission time Handle Problem Language Result Execution time Memory
246930 2020-07-10T15:09:02 Z patrikpavic2 Robots (APIO13_robots) C++17
60 / 100
 833 ms 163844 KB 
#include <cstdio>
#include <cstring>
#include <vector>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef pair < int, int > pii;

const int N = 505;
const int INF = 0x3f3f3f3f;

const int px[4] = {-1, 0, 1, 0};
const int py[4] = {0, 1, 0, -1};

int dis[N][N][46];
int tmp[N][N][5], obr[N][N][5];
vector < pair < pii, int > > kad[N * N];
int L[N], R[N], kod[11][11];
int n, m, rob;
char s[N][N];


void obradi(int k){
	memset(obr, 0, sizeof(obr));
	memset(tmp, INF, sizeof(tmp));
	for(int i = 0;i < n;i++){
		for(int j = 0;j < m;j++){
			tmp[i][j][4] = dis[i][j][k];
			if(tmp[i][j][4] != INF)
				kad[tmp[i][j][4]].PB({{i, j}, 4});
		}
	}
	for(int sad = 0;sad < n * m;sad++){
		for(int i = 0;i < (int)kad[sad].size();i++){
			int x = kad[sad][i].X.X, y = kad[sad][i].X.Y;
			int sm = kad[sad][i].Y; 
			//printf("trenutno (%d %d) sm = %d udaljenost = %d\n", x, y, sm, sad);
			if(obr[x][y][sm]) continue;
			obr[x][y][sm] = 1;
			if(sm != 4){
				if(s[x][y] == 'C') sm = (sm + 1) % 4;
				if(s[x][y] == 'A') sm = (sm + 3) % 4;
				int nx = x + px[sm], ny = y + py[sm];	
				if(s[nx][ny] == 'x'){
					if(sad < tmp[x][y][4]){
						tmp[x][y][4] = sad;
						kad[sad].PB({{x, y}, 4});
					}
				}
				else{
					if(sad < tmp[nx][ny][sm]){
						tmp[nx][ny][sm] = sad;
						kad[sad].PB({{nx, ny}, sm});
					}
				}
			}
			else{
				for(int nsm = 0;nsm < 4;nsm++){
					if(sad + 1 < tmp[x][y][nsm]){
						tmp[x][y][nsm] = sad + 1;
						kad[sad + 1].PB({{x, y}, nsm});
					}
				}
				
			}
		}
		kad[sad].clear();
	}
	for(int i = 0;i < n;i++){
		for(int j = 0;j < m;j++){
			if(tmp[i][j][4] != INF){
				//printf("do (%d %d) u %d koraka\n", i,j, tmp[i][j][4]);
				dis[i][j][k] = tmp[i][j][4];
			}
		}
	}
}

void pripremi(){
	int gdje = 0;
	for(int ln = 1;ln <= rob;ln++){
		for(int i = 1;i + ln - 1 <= rob;i++){
			L[gdje] = i; R[gdje] = i + ln - 1;
			kod[L[gdje]][R[gdje]] = gdje; gdje++;
		}
	}
}

void spajaj(int k){
	int l = L[k], r = R[k];
	//printf("spajam %d tj. [%d %d]\n", k, l, r);
	if(l != r){
		for(int i = 0;i < n;i++){
			for(int j = 0;j < m;j++){
				if(s[i][j] == 'x') continue;
				for(int ct = l;ct < r;ct++){
					//printf("%d + %d\n", dis[i][j][kod[l][ct]],  dis[i][j][kod[ct + 1][r]]);
					dis[i][j][k] = min(dis[i][j][k], dis[i][j][kod[l][ct]] + dis[i][j][kod[ct + 1][r]]);
				}
			}
		}
	}
	else{
		for(int i = 0;i < n;i++){
			for(int j = 0;j < m;j++){
				if(s[i][j] == '0' + l)
					dis[i][j][k] = 0;
			}
		}
	}
	//printf("obradujem %d tj. [%d %d]\n", k, l, r);
	obradi(k);
	//printf("obradio\n");
}

int main(){
	memset(dis, INF, sizeof(dis));
	scanf("%d%d%d", &rob, &m, &n);
	n += 2, m += 2;
	for(int i = 0;i < m;i++)
		s[n - 1][i] = 'x', s[0][i] = 'x';
	for(int i = 0;i < n;i++)
		s[i][m - 1] = 'x', s[i][0] = 'x'; 
	for(int i = 1;i + 1 < n;i++)
		for(int j = 1;j + 1 < m;j++)
			scanf(" %c", &s[i][j]);	
	pripremi();
	for(int i = 0;i < rob * (rob + 1) / 2;i++)
		spajaj(i);
	int ans = INF;
	for(int i = 0;i < n;i++)
		for(int j = 0;j < m;j++)
			ans = min(ans, dis[i][j][rob * (rob + 1) / 2 - 1]);
	printf("%d\n", (ans == INF ? -1 : ans));
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:122:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &rob, &m, &n);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
robots.cpp:130:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf(" %c", &s[i][j]); 
    ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 62220 KB Output is correct
2 Correct 38 ms 62200 KB Output is correct
3 Correct 38 ms 62208 KB Output is correct
4 Correct 38 ms 62208 KB Output is correct
5 Correct 39 ms 62204 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 62220 KB Output is correct
2 Correct 38 ms 62200 KB Output is correct
3 Correct 38 ms 62208 KB Output is correct
4 Correct 38 ms 62208 KB Output is correct
5 Correct 39 ms 62204 KB Output is correct
6 Correct 39 ms 62200 KB Output is correct
7 Correct 38 ms 62208 KB Output is correct
8 Correct 38 ms 62200 KB Output is correct
9 Correct 38 ms 62208 KB Output is correct
10 Correct 36 ms 62080 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 62220 KB Output is correct
2 Correct 38 ms 62200 KB Output is correct
3 Correct 38 ms 62208 KB Output is correct
4 Correct 38 ms 62208 KB Output is correct
5 Correct 39 ms 62204 KB Output is correct
6 Correct 39 ms 62200 KB Output is correct
7 Correct 38 ms 62208 KB Output is correct
8 Correct 38 ms 62200 KB Output is correct
9 Correct 38 ms 62208 KB Output is correct
10 Correct 36 ms 62080 KB Output is correct
11 Correct 360 ms 91352 KB Output is correct
12 Correct 57 ms 66040 KB Output is correct
13 Correct 247 ms 76860 KB Output is correct
14 Correct 488 ms 105432 KB Output is correct
15 Correct 260 ms 68932 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 62220 KB Output is correct
2 Correct 38 ms 62200 KB Output is correct
3 Correct 38 ms 62208 KB Output is correct
4 Correct 38 ms 62208 KB Output is correct
5 Correct 39 ms 62204 KB Output is correct
6 Correct 39 ms 62200 KB Output is correct
7 Correct 38 ms 62208 KB Output is correct
8 Correct 38 ms 62200 KB Output is correct
9 Correct 38 ms 62208 KB Output is correct
10 Correct 36 ms 62080 KB Output is correct
11 Correct 360 ms 91352 KB Output is correct
12 Correct 57 ms 66040 KB Output is correct
13 Correct 247 ms 76860 KB Output is correct
14 Correct 488 ms 105432 KB Output is correct
15 Correct 260 ms 68932 KB Output is correct
16 Correct 466 ms 64152 KB Output is correct
17 Runtime error 833 ms 163844 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -