oj.uz

Submission #733728

# Submission time Handle Problem Language Result Execution time Memory
733728 2023-05-01T08:34:37 Z minhcool Mars (APIO22_mars) C++17
44 / 100
 349 ms 49240 KB 
#include "mars.h"
#include<bits/stdc++.h>
using namespace std;
 
#define fi first
#define se second
#define pb push_back
#define mp make_pair
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 35;
 
const int oo = 1e18 + 7, mod = 1e9 + 7;
 
vector<ii> route[N][N][N];
int cnt[N][N][N][N];
ii save[N][N][N][N][105];// cell (i, j) at phase k, the h-th bit will save the value of what node
 
void prep(int id){// preparing the route for (i, j)
	// in order to get 36, we don't need the SA the path
    if(route[id][0][0].size()) return;
	int n = id;
	for(int i = 0; i < (2 * n + 1); i++){
		for(int j = 0; j < (2 * n + 1); j++){
			route[id][i][j].clear();
			for(int k = 0; k < (2 * n + 1); k++) cnt[id][i][j][k] = 0;
		}
	}
	for(int i = 2 * n; i >= 0; i--){
		for(int j = 2 * n; j >= 0; j--){
			/*
			for(int k = 0; k < n; k++){
				route[id][i][j].pb({i - 2 * max(0, min(k, (i - 1) / 2)), j - 2 * max(0, min(k, (j - 1) / 2))});
			}*/
			route[id][i][j].pb({i, j});
			ii lst = {i, j};
			for(int k = 1; k < n; k++){
				//route[id][i][j].pb({i - 2 * max(0, min(k, (i - 1) / 2)), j - 2 * max(0, min(k, (j - 1) / 2))});
				bool ck = 1;
				vector<pair<int, ii>> cans;
				for(int temp1 = -2; temp1 <= 0; temp1++){
					if(!ck) break;
					for(int temp2 = -2; temp2 <= 0; temp2++){
						if((lst.fi + temp1) < 0 || (lst.se + temp2) < 0) continue;
                        if((lst.fi + temp1) > (2 * n - 2 * k)  || (lst.se + temp2) > (2 * n - 2 * k)) continue;
						if(cnt[id][lst.fi + temp1][lst.se + temp2][k] >= 100) continue;
						cans.pb({cnt[id][lst.fi + temp1][lst.se + temp2][k] - 10 * (temp1 + temp2), {lst.fi + temp1, lst.se + temp2}});
						//ck = 0;
						//break;
					}
				}
				sort(cans.begin(), cans.end());
				route[id][i][j].pb({cans[0].se.fi, cans[0].se.se});
				lst = {cans[0].se.fi, cans[0].se.se};
              //assert(!ck);
			}
			int itr = 0;
			for(auto it : route[id][i][j]){
				//cout << i << " " << j << " " << it.fi << " " << it.se << " " << itr << "\n";
				save[id][it.fi][it.se][itr][cnt[id][it.fi][it.se][itr]] = {i, j};
				cnt[id][it.fi][it.se][itr]++;
				itr++;
			}
		}	
	}
	for(int i = 0; i <= 2 * n; i++){
		for(int j = 0; j <= 2 * n; j++){
			for(int k = 0; k < n; k++){
				for(int kk = 0; kk < cnt[id][i][j][k]; kk++){
					//cout << i << " " << j << " " << k << " " << kk << " " << save[i][j][k][kk].fi << " " << save[i][j][k][kk].se << "\n";	
				}
			}	
		}
	}
}
 
bool vis[N][N];
int val[N][N];
 
void ff(int i, int j, int n){
	//cout << i << " " << j << "\n";
	if(i < 0 || j < 0 || i >= (2 * n + 1) || j >= (2 * n + 1) || !val[i][j]) return;
	val[i][j] = 0;
	ff(i + 1, j, n);
	ff(i - 1, j, n);
	ff(i, j - 1, n);
	ff(i, j + 1, n);
}
 
string process(vector<vector<string>> a, int i, int j, int k, int n){
	prep(n);
	//cout << "OK\n";
	for(int ii = 0; ii <= 2 * n; ii++){
		for(int jj = 0; jj <= 2 * n; jj++) vis[ii][jj] = 0;
	}
	for(int ii = 0; ii <= 2; ii++){
		for(int jj = 0; jj <= 2; jj++){
			for(int kk = 0; kk < cnt[n][i + ii][j + jj][k]; kk++){
				int x = save[n][i + ii][j + jj][k][kk].fi, y = save[n][i + ii][j + jj][k][kk].se;
				val[x][y] = a[ii][jj][kk] - '0';
				vis[x][y] = 1;
				//cout << i << " " << j << " " << k << " " << x << " " << y << " " << val[x][y] << "\n";
			}
		}
	}
	if(k == n - 1){
		//exit(0);
		int ans = 0;
		/*
		for(int i = 0; i < (2 * n) + 1; i++){
			for(int j = 0; j < (2 * n) + 1; j++) cout << val[i][j] << " ";
			cout << "\n";
		}*/
		for(int i = 0; i < (2 * n + 1); i++){
			for(int j = 0; j < (2 * n + 1); j++){
				assert(vis[i][j]);
			//	cout << "OK " << i << " " << j << " " << val[i][j] << "\n";
				if(!val[i][j]) continue;
				ans++;
				ff(i, j, n);
			}
		}
		//cout << ans << "\n";
		string temp;
		for(int kk = 0; kk < 100; kk++) temp += '0';
		for(int kk = 0; kk < 20; kk++) if(ans & (1LL << kk)) temp[kk] = '1';
		return temp;
	}
	else{
		string temp;
		for(int kk = 0; kk < 100; kk++) temp += '0';
		for(int kk = 0; kk < cnt[n][i][j][k + 1]; kk++){
			int x = save[n][i][j][k + 1][kk].fi, y = save[n][i][j][k + 1][kk].se;
			assert(vis[x][y]);
			temp[kk] = char(48 + val[x][y]);
		}
		return temp;
	}
}

Compilation message

mars.cpp:16:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   16 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 11196 KB Output is correct
2 Correct 15 ms 11384 KB Output is correct
3 Correct 14 ms 11236 KB Output is correct
4 Correct 15 ms 11460 KB Output is correct
5 Correct 15 ms 11248 KB Output is correct
6 Correct 13 ms 11344 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 11196 KB Output is correct
2 Correct 15 ms 11384 KB Output is correct
3 Correct 14 ms 11236 KB Output is correct
4 Correct 15 ms 11460 KB Output is correct
5 Correct 15 ms 11248 KB Output is correct
6 Correct 13 ms 11344 KB Output is correct
7 Correct 23 ms 16372 KB Output is correct
8 Correct 28 ms 13780 KB Output is correct
9 Correct 27 ms 13720 KB Output is correct
10 Correct 28 ms 13700 KB Output is correct
11 Correct 26 ms 13576 KB Output is correct
12 Correct 26 ms 13588 KB Output is correct
13 Correct 27 ms 13576 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 11196 KB Output is correct
2 Correct 15 ms 11384 KB Output is correct
3 Correct 14 ms 11236 KB Output is correct
4 Correct 15 ms 11460 KB Output is correct
5 Correct 15 ms 11248 KB Output is correct
6 Correct 13 ms 11344 KB Output is correct
7 Correct 23 ms 16372 KB Output is correct
8 Correct 28 ms 13780 KB Output is correct
9 Correct 27 ms 13720 KB Output is correct
10 Correct 28 ms 13700 KB Output is correct
11 Correct 26 ms 13576 KB Output is correct
12 Correct 26 ms 13588 KB Output is correct
13 Correct 27 ms 13576 KB Output is correct
14 Correct 52 ms 24600 KB Output is correct
15 Correct 59 ms 19072 KB Output is correct
16 Correct 62 ms 18992 KB Output is correct
17 Correct 59 ms 18988 KB Output is correct
18 Correct 59 ms 18992 KB Output is correct
19 Correct 59 ms 19016 KB Output is correct
20 Correct 53 ms 19004 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 11196 KB Output is correct
2 Correct 15 ms 11384 KB Output is correct
3 Correct 14 ms 11236 KB Output is correct
4 Correct 15 ms 11460 KB Output is correct
5 Correct 15 ms 11248 KB Output is correct
6 Correct 13 ms 11344 KB Output is correct
7 Correct 23 ms 16372 KB Output is correct
8 Correct 28 ms 13780 KB Output is correct
9 Correct 27 ms 13720 KB Output is correct
10 Correct 28 ms 13700 KB Output is correct
11 Correct 26 ms 13576 KB Output is correct
12 Correct 26 ms 13588 KB Output is correct
13 Correct 27 ms 13576 KB Output is correct
14 Correct 52 ms 24600 KB Output is correct
15 Correct 59 ms 19072 KB Output is correct
16 Correct 62 ms 18992 KB Output is correct
17 Correct 59 ms 18988 KB Output is correct
18 Correct 59 ms 18992 KB Output is correct
19 Correct 59 ms 19016 KB Output is correct
20 Correct 53 ms 19004 KB Output is correct
21 Correct 83 ms 22020 KB Output is correct
22 Correct 110 ms 25804 KB Output is correct
23 Correct 117 ms 25820 KB Output is correct
24 Correct 112 ms 25848 KB Output is correct
25 Correct 117 ms 25904 KB Output is correct
26 Correct 114 ms 25816 KB Output is correct
27 Correct 115 ms 25808 KB Output is correct
28 Correct 106 ms 25872 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 11196 KB Output is correct
2 Correct 15 ms 11384 KB Output is correct
3 Correct 14 ms 11236 KB Output is correct
4 Correct 15 ms 11460 KB Output is correct
5 Correct 15 ms 11248 KB Output is correct
6 Correct 13 ms 11344 KB Output is correct
7 Correct 23 ms 16372 KB Output is correct
8 Correct 28 ms 13780 KB Output is correct
9 Correct 27 ms 13720 KB Output is correct
10 Correct 28 ms 13700 KB Output is correct
11 Correct 26 ms 13576 KB Output is correct
12 Correct 26 ms 13588 KB Output is correct
13 Correct 27 ms 13576 KB Output is correct
14 Correct 52 ms 24600 KB Output is correct
15 Correct 59 ms 19072 KB Output is correct
16 Correct 62 ms 18992 KB Output is correct
17 Correct 59 ms 18988 KB Output is correct
18 Correct 59 ms 18992 KB Output is correct
19 Correct 59 ms 19016 KB Output is correct
20 Correct 53 ms 19004 KB Output is correct
21 Correct 83 ms 22020 KB Output is correct
22 Correct 110 ms 25804 KB Output is correct
23 Correct 117 ms 25820 KB Output is correct
24 Correct 112 ms 25848 KB Output is correct
25 Correct 117 ms 25904 KB Output is correct
26 Correct 114 ms 25816 KB Output is correct
27 Correct 115 ms 25808 KB Output is correct
28 Correct 106 ms 25872 KB Output is correct
29 Correct 155 ms 30840 KB Output is correct
30 Correct 215 ms 36064 KB Output is correct
31 Correct 203 ms 35984 KB Output is correct
32 Correct 207 ms 36108 KB Output is correct
33 Correct 213 ms 35952 KB Output is correct
34 Correct 205 ms 35944 KB Output is correct
35 Correct 223 ms 35964 KB Output is correct
36 Correct 208 ms 35928 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 11196 KB Output is correct
2 Correct 15 ms 11384 KB Output is correct
3 Correct 14 ms 11236 KB Output is correct
4 Correct 15 ms 11460 KB Output is correct
5 Correct 15 ms 11248 KB Output is correct
6 Correct 13 ms 11344 KB Output is correct
7 Correct 23 ms 16372 KB Output is correct
8 Correct 28 ms 13780 KB Output is correct
9 Correct 27 ms 13720 KB Output is correct
10 Correct 28 ms 13700 KB Output is correct
11 Correct 26 ms 13576 KB Output is correct
12 Correct 26 ms 13588 KB Output is correct
13 Correct 27 ms 13576 KB Output is correct
14 Correct 52 ms 24600 KB Output is correct
15 Correct 59 ms 19072 KB Output is correct
16 Correct 62 ms 18992 KB Output is correct
17 Correct 59 ms 18988 KB Output is correct
18 Correct 59 ms 18992 KB Output is correct
19 Correct 59 ms 19016 KB Output is correct
20 Correct 53 ms 19004 KB Output is correct
21 Correct 83 ms 22020 KB Output is correct
22 Correct 110 ms 25804 KB Output is correct
23 Correct 117 ms 25820 KB Output is correct
24 Correct 112 ms 25848 KB Output is correct
25 Correct 117 ms 25904 KB Output is correct
26 Correct 114 ms 25816 KB Output is correct
27 Correct 115 ms 25808 KB Output is correct
28 Correct 106 ms 25872 KB Output is correct
29 Correct 155 ms 30840 KB Output is correct
30 Correct 215 ms 36064 KB Output is correct
31 Correct 203 ms 35984 KB Output is correct
32 Correct 207 ms 36108 KB Output is correct
33 Correct 213 ms 35952 KB Output is correct
34 Correct 205 ms 35944 KB Output is correct
35 Correct 223 ms 35964 KB Output is correct
36 Correct 208 ms 35928 KB Output is correct
37 Correct 265 ms 42048 KB Output is correct
38 Correct 332 ms 49148 KB Output is correct
39 Correct 324 ms 49232 KB Output is correct
40 Correct 349 ms 49192 KB Output is correct
41 Correct 336 ms 49204 KB Output is correct
42 Correct 337 ms 49240 KB Output is correct
43 Correct 323 ms 49208 KB Output is correct
44 Correct 340 ms 49228 KB Output is correct

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 11196 KB Output is correct
2 Correct 15 ms 11384 KB Output is correct
3 Correct 14 ms 11236 KB Output is correct
4 Correct 15 ms 11460 KB Output is correct
5 Correct 15 ms 11248 KB Output is correct
6 Correct 13 ms 11344 KB Output is correct
7 Correct 23 ms 16372 KB Output is correct
8 Correct 28 ms 13780 KB Output is correct
9 Correct 27 ms 13720 KB Output is correct
10 Correct 28 ms 13700 KB Output is correct
11 Correct 26 ms 13576 KB Output is correct
12 Correct 26 ms 13588 KB Output is correct
13 Correct 27 ms 13576 KB Output is correct
14 Correct 52 ms 24600 KB Output is correct
15 Correct 59 ms 19072 KB Output is correct
16 Correct 62 ms 18992 KB Output is correct
17 Correct 59 ms 18988 KB Output is correct
18 Correct 59 ms 18992 KB Output is correct
19 Correct 59 ms 19016 KB Output is correct
20 Correct 53 ms 19004 KB Output is correct
21 Correct 83 ms 22020 KB Output is correct
22 Correct 110 ms 25804 KB Output is correct
23 Correct 117 ms 25820 KB Output is correct
24 Correct 112 ms 25848 KB Output is correct
25 Correct 117 ms 25904 KB Output is correct
26 Correct 114 ms 25816 KB Output is correct
27 Correct 115 ms 25808 KB Output is correct
28 Correct 106 ms 25872 KB Output is correct
29 Correct 155 ms 30840 KB Output is correct
30 Correct 215 ms 36064 KB Output is correct
31 Correct 203 ms 35984 KB Output is correct
32 Correct 207 ms 36108 KB Output is correct
33 Correct 213 ms 35952 KB Output is correct
34 Correct 205 ms 35944 KB Output is correct
35 Correct 223 ms 35964 KB Output is correct
36 Correct 208 ms 35928 KB Output is correct
37 Correct 265 ms 42048 KB Output is correct
38 Correct 332 ms 49148 KB Output is correct
39 Correct 324 ms 49232 KB Output is correct
40 Correct 349 ms 49192 KB Output is correct
41 Correct 336 ms 49204 KB Output is correct
42 Correct 337 ms 49240 KB Output is correct
43 Correct 323 ms 49208 KB Output is correct
44 Correct 340 ms 49228 KB Output is correct
45 Runtime error 32 ms 11848 KB Execution killed with signal 11
46 Halted 0 ms 0 KB -

Subtask #8
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 11196 KB Output is correct
2 Correct 15 ms 11384 KB Output is correct
3 Correct 14 ms 11236 KB Output is correct
4 Correct 15 ms 11460 KB Output is correct
5 Correct 15 ms 11248 KB Output is correct
6 Correct 13 ms 11344 KB Output is correct
7 Correct 23 ms 16372 KB Output is correct
8 Correct 28 ms 13780 KB Output is correct
9 Correct 27 ms 13720 KB Output is correct
10 Correct 28 ms 13700 KB Output is correct
11 Correct 26 ms 13576 KB Output is correct
12 Correct 26 ms 13588 KB Output is correct
13 Correct 27 ms 13576 KB Output is correct
14 Correct 52 ms 24600 KB Output is correct
15 Correct 59 ms 19072 KB Output is correct
16 Correct 62 ms 18992 KB Output is correct
17 Correct 59 ms 18988 KB Output is correct
18 Correct 59 ms 18992 KB Output is correct
19 Correct 59 ms 19016 KB Output is correct
20 Correct 53 ms 19004 KB Output is correct
21 Correct 83 ms 22020 KB Output is correct
22 Correct 110 ms 25804 KB Output is correct
23 Correct 117 ms 25820 KB Output is correct
24 Correct 112 ms 25848 KB Output is correct
25 Correct 117 ms 25904 KB Output is correct
26 Correct 114 ms 25816 KB Output is correct
27 Correct 115 ms 25808 KB Output is correct
28 Correct 106 ms 25872 KB Output is correct
29 Correct 155 ms 30840 KB Output is correct
30 Correct 215 ms 36064 KB Output is correct
31 Correct 203 ms 35984 KB Output is correct
32 Correct 207 ms 36108 KB Output is correct
33 Correct 213 ms 35952 KB Output is correct
34 Correct 205 ms 35944 KB Output is correct
35 Correct 223 ms 35964 KB Output is correct
36 Correct 208 ms 35928 KB Output is correct
37 Correct 265 ms 42048 KB Output is correct
38 Correct 332 ms 49148 KB Output is correct
39 Correct 324 ms 49232 KB Output is correct
40 Correct 349 ms 49192 KB Output is correct
41 Correct 336 ms 49204 KB Output is correct
42 Correct 337 ms 49240 KB Output is correct
43 Correct 323 ms 49208 KB Output is correct
44 Correct 340 ms 49228 KB Output is correct
45 Runtime error 32 ms 11848 KB Execution killed with signal 11
46 Halted 0 ms 0 KB -

Subtask #9
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 11196 KB Output is correct
2 Correct 15 ms 11384 KB Output is correct
3 Correct 14 ms 11236 KB Output is correct
4 Correct 15 ms 11460 KB Output is correct
5 Correct 15 ms 11248 KB Output is correct
6 Correct 13 ms 11344 KB Output is correct
7 Correct 23 ms 16372 KB Output is correct
8 Correct 28 ms 13780 KB Output is correct
9 Correct 27 ms 13720 KB Output is correct
10 Correct 28 ms 13700 KB Output is correct
11 Correct 26 ms 13576 KB Output is correct
12 Correct 26 ms 13588 KB Output is correct
13 Correct 27 ms 13576 KB Output is correct
14 Correct 52 ms 24600 KB Output is correct
15 Correct 59 ms 19072 KB Output is correct
16 Correct 62 ms 18992 KB Output is correct
17 Correct 59 ms 18988 KB Output is correct
18 Correct 59 ms 18992 KB Output is correct
19 Correct 59 ms 19016 KB Output is correct
20 Correct 53 ms 19004 KB Output is correct
21 Correct 83 ms 22020 KB Output is correct
22 Correct 110 ms 25804 KB Output is correct
23 Correct 117 ms 25820 KB Output is correct
24 Correct 112 ms 25848 KB Output is correct
25 Correct 117 ms 25904 KB Output is correct
26 Correct 114 ms 25816 KB Output is correct
27 Correct 115 ms 25808 KB Output is correct
28 Correct 106 ms 25872 KB Output is correct
29 Correct 155 ms 30840 KB Output is correct
30 Correct 215 ms 36064 KB Output is correct
31 Correct 203 ms 35984 KB Output is correct
32 Correct 207 ms 36108 KB Output is correct
33 Correct 213 ms 35952 KB Output is correct
34 Correct 205 ms 35944 KB Output is correct
35 Correct 223 ms 35964 KB Output is correct
36 Correct 208 ms 35928 KB Output is correct
37 Correct 265 ms 42048 KB Output is correct
38 Correct 332 ms 49148 KB Output is correct
39 Correct 324 ms 49232 KB Output is correct
40 Correct 349 ms 49192 KB Output is correct
41 Correct 336 ms 49204 KB Output is correct
42 Correct 337 ms 49240 KB Output is correct
43 Correct 323 ms 49208 KB Output is correct
44 Correct 340 ms 49228 KB Output is correct
45 Runtime error 32 ms 11848 KB Execution killed with signal 11
46 Halted 0 ms 0 KB -

Subtask #10
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 11196 KB Output is correct
2 Correct 15 ms 11384 KB Output is correct
3 Correct 14 ms 11236 KB Output is correct
4 Correct 15 ms 11460 KB Output is correct
5 Correct 15 ms 11248 KB Output is correct
6 Correct 13 ms 11344 KB Output is correct
7 Correct 23 ms 16372 KB Output is correct
8 Correct 28 ms 13780 KB Output is correct
9 Correct 27 ms 13720 KB Output is correct
10 Correct 28 ms 13700 KB Output is correct
11 Correct 26 ms 13576 KB Output is correct
12 Correct 26 ms 13588 KB Output is correct
13 Correct 27 ms 13576 KB Output is correct
14 Correct 52 ms 24600 KB Output is correct
15 Correct 59 ms 19072 KB Output is correct
16 Correct 62 ms 18992 KB Output is correct
17 Correct 59 ms 18988 KB Output is correct
18 Correct 59 ms 18992 KB Output is correct
19 Correct 59 ms 19016 KB Output is correct
20 Correct 53 ms 19004 KB Output is correct
21 Correct 83 ms 22020 KB Output is correct
22 Correct 110 ms 25804 KB Output is correct
23 Correct 117 ms 25820 KB Output is correct
24 Correct 112 ms 25848 KB Output is correct
25 Correct 117 ms 25904 KB Output is correct
26 Correct 114 ms 25816 KB Output is correct
27 Correct 115 ms 25808 KB Output is correct
28 Correct 106 ms 25872 KB Output is correct
29 Correct 155 ms 30840 KB Output is correct
30 Correct 215 ms 36064 KB Output is correct
31 Correct 203 ms 35984 KB Output is correct
32 Correct 207 ms 36108 KB Output is correct
33 Correct 213 ms 35952 KB Output is correct
34 Correct 205 ms 35944 KB Output is correct
35 Correct 223 ms 35964 KB Output is correct
36 Correct 208 ms 35928 KB Output is correct
37 Correct 265 ms 42048 KB Output is correct
38 Correct 332 ms 49148 KB Output is correct
39 Correct 324 ms 49232 KB Output is correct
40 Correct 349 ms 49192 KB Output is correct
41 Correct 336 ms 49204 KB Output is correct
42 Correct 337 ms 49240 KB Output is correct
43 Correct 323 ms 49208 KB Output is correct
44 Correct 340 ms 49228 KB Output is correct
45 Runtime error 32 ms 11848 KB Execution killed with signal 11
46 Halted 0 ms 0 KB -