oj.uz

Submission #246931

# Submission time Handle Problem Language Result Execution time Memory
246931 2020-07-10T15:09:34 Z patrikpavic2 Robots (APIO13_robots) C++17
60 / 100
 864 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 = 515;
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 40 ms 64644 KB Output is correct
2 Correct 38 ms 64616 KB Output is correct
3 Correct 38 ms 64640 KB Output is correct
4 Correct 39 ms 64760 KB Output is correct
5 Correct 39 ms 64768 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 64644 KB Output is correct
2 Correct 38 ms 64616 KB Output is correct
3 Correct 38 ms 64640 KB Output is correct
4 Correct 39 ms 64760 KB Output is correct
5 Correct 39 ms 64768 KB Output is correct
6 Correct 40 ms 64632 KB Output is correct
7 Correct 40 ms 64640 KB Output is correct
8 Correct 39 ms 64760 KB Output is correct
9 Correct 39 ms 64760 KB Output is correct
10 Correct 41 ms 64760 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 64644 KB Output is correct
2 Correct 38 ms 64616 KB Output is correct
3 Correct 38 ms 64640 KB Output is correct
4 Correct 39 ms 64760 KB Output is correct
5 Correct 39 ms 64768 KB Output is correct
6 Correct 40 ms 64632 KB Output is correct
7 Correct 40 ms 64640 KB Output is correct
8 Correct 39 ms 64760 KB Output is correct
9 Correct 39 ms 64760 KB Output is correct
10 Correct 41 ms 64760 KB Output is correct
11 Correct 335 ms 93800 KB Output is correct
12 Correct 52 ms 68472 KB Output is correct
13 Correct 265 ms 79412 KB Output is correct
14 Correct 520 ms 107896 KB Output is correct
15 Correct 271 ms 71492 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 64644 KB Output is correct
2 Correct 38 ms 64616 KB Output is correct
3 Correct 38 ms 64640 KB Output is correct
4 Correct 39 ms 64760 KB Output is correct
5 Correct 39 ms 64768 KB Output is correct
6 Correct 40 ms 64632 KB Output is correct
7 Correct 40 ms 64640 KB Output is correct
8 Correct 39 ms 64760 KB Output is correct
9 Correct 39 ms 64760 KB Output is correct
10 Correct 41 ms 64760 KB Output is correct
11 Correct 335 ms 93800 KB Output is correct
12 Correct 52 ms 68472 KB Output is correct
13 Correct 265 ms 79412 KB Output is correct
14 Correct 520 ms 107896 KB Output is correct
15 Correct 271 ms 71492 KB Output is correct
16 Correct 495 ms 66424 KB Output is correct
17 Runtime error 864 ms 163844 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -