oj.uz

Submission #733725

# Submission time Handle Problem Language Result Execution time Memory
733725 2023-05-01T08:32:56 Z minhcool Mars (APIO22_mars) C++17
29 / 100
 4000 ms 30864 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
	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 13 ms 11556 KB Output is correct
2 Correct 13 ms 11080 KB Output is correct
3 Correct 15 ms 11512 KB Output is correct
4 Correct 15 ms 11272 KB Output is correct
5 Correct 16 ms 11396 KB Output is correct
6 Correct 15 ms 11084 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 11556 KB Output is correct
2 Correct 13 ms 11080 KB Output is correct
3 Correct 15 ms 11512 KB Output is correct
4 Correct 15 ms 11272 KB Output is correct
5 Correct 16 ms 11396 KB Output is correct
6 Correct 15 ms 11084 KB Output is correct
7 Correct 32 ms 16380 KB Output is correct
8 Correct 67 ms 13880 KB Output is correct
9 Correct 66 ms 13684 KB Output is correct
10 Correct 56 ms 13532 KB Output is correct
11 Correct 61 ms 13548 KB Output is correct
12 Correct 57 ms 13792 KB Output is correct
13 Correct 63 ms 13660 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 11556 KB Output is correct
2 Correct 13 ms 11080 KB Output is correct
3 Correct 15 ms 11512 KB Output is correct
4 Correct 15 ms 11272 KB Output is correct
5 Correct 16 ms 11396 KB Output is correct
6 Correct 15 ms 11084 KB Output is correct
7 Correct 32 ms 16380 KB Output is correct
8 Correct 67 ms 13880 KB Output is correct
9 Correct 66 ms 13684 KB Output is correct
10 Correct 56 ms 13532 KB Output is correct
11 Correct 61 ms 13548 KB Output is correct
12 Correct 57 ms 13792 KB Output is correct
13 Correct 63 ms 13660 KB Output is correct
14 Correct 216 ms 24584 KB Output is correct
15 Correct 461 ms 19000 KB Output is correct
16 Correct 445 ms 18992 KB Output is correct
17 Correct 473 ms 18988 KB Output is correct
18 Correct 462 ms 18996 KB Output is correct
19 Correct 465 ms 19116 KB Output is correct
20 Correct 459 ms 19044 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 11556 KB Output is correct
2 Correct 13 ms 11080 KB Output is correct
3 Correct 15 ms 11512 KB Output is correct
4 Correct 15 ms 11272 KB Output is correct
5 Correct 16 ms 11396 KB Output is correct
6 Correct 15 ms 11084 KB Output is correct
7 Correct 32 ms 16380 KB Output is correct
8 Correct 67 ms 13880 KB Output is correct
9 Correct 66 ms 13684 KB Output is correct
10 Correct 56 ms 13532 KB Output is correct
11 Correct 61 ms 13548 KB Output is correct
12 Correct 57 ms 13792 KB Output is correct
13 Correct 63 ms 13660 KB Output is correct
14 Correct 216 ms 24584 KB Output is correct
15 Correct 461 ms 19000 KB Output is correct
16 Correct 445 ms 18992 KB Output is correct
17 Correct 473 ms 18988 KB Output is correct
18 Correct 462 ms 18996 KB Output is correct
19 Correct 465 ms 19116 KB Output is correct
20 Correct 459 ms 19044 KB Output is correct
21 Correct 1067 ms 22076 KB Output is correct
22 Correct 2299 ms 25820 KB Output is correct
23 Correct 2409 ms 25868 KB Output is correct
24 Correct 2300 ms 25980 KB Output is correct
25 Correct 2299 ms 25808 KB Output is correct
26 Correct 2164 ms 25796 KB Output is correct
27 Correct 2205 ms 26056 KB Output is correct
28 Correct 2128 ms 25808 KB Output is correct

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 11556 KB Output is correct
2 Correct 13 ms 11080 KB Output is correct
3 Correct 15 ms 11512 KB Output is correct
4 Correct 15 ms 11272 KB Output is correct
5 Correct 16 ms 11396 KB Output is correct
6 Correct 15 ms 11084 KB Output is correct
7 Correct 32 ms 16380 KB Output is correct
8 Correct 67 ms 13880 KB Output is correct
9 Correct 66 ms 13684 KB Output is correct
10 Correct 56 ms 13532 KB Output is correct
11 Correct 61 ms 13548 KB Output is correct
12 Correct 57 ms 13792 KB Output is correct
13 Correct 63 ms 13660 KB Output is correct
14 Correct 216 ms 24584 KB Output is correct
15 Correct 461 ms 19000 KB Output is correct
16 Correct 445 ms 18992 KB Output is correct
17 Correct 473 ms 18988 KB Output is correct
18 Correct 462 ms 18996 KB Output is correct
19 Correct 465 ms 19116 KB Output is correct
20 Correct 459 ms 19044 KB Output is correct
21 Correct 1067 ms 22076 KB Output is correct
22 Correct 2299 ms 25820 KB Output is correct
23 Correct 2409 ms 25868 KB Output is correct
24 Correct 2300 ms 25980 KB Output is correct
25 Correct 2299 ms 25808 KB Output is correct
26 Correct 2164 ms 25796 KB Output is correct
27 Correct 2205 ms 26056 KB Output is correct
28 Correct 2128 ms 25808 KB Output is correct
29 Execution timed out 4000 ms 30864 KB
30 Halted 0 ms 0 KB -

Subtask #6
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 11556 KB Output is correct
2 Correct 13 ms 11080 KB Output is correct
3 Correct 15 ms 11512 KB Output is correct
4 Correct 15 ms 11272 KB Output is correct
5 Correct 16 ms 11396 KB Output is correct
6 Correct 15 ms 11084 KB Output is correct
7 Correct 32 ms 16380 KB Output is correct
8 Correct 67 ms 13880 KB Output is correct
9 Correct 66 ms 13684 KB Output is correct
10 Correct 56 ms 13532 KB Output is correct
11 Correct 61 ms 13548 KB Output is correct
12 Correct 57 ms 13792 KB Output is correct
13 Correct 63 ms 13660 KB Output is correct
14 Correct 216 ms 24584 KB Output is correct
15 Correct 461 ms 19000 KB Output is correct
16 Correct 445 ms 18992 KB Output is correct
17 Correct 473 ms 18988 KB Output is correct
18 Correct 462 ms 18996 KB Output is correct
19 Correct 465 ms 19116 KB Output is correct
20 Correct 459 ms 19044 KB Output is correct
21 Correct 1067 ms 22076 KB Output is correct
22 Correct 2299 ms 25820 KB Output is correct
23 Correct 2409 ms 25868 KB Output is correct
24 Correct 2300 ms 25980 KB Output is correct
25 Correct 2299 ms 25808 KB Output is correct
26 Correct 2164 ms 25796 KB Output is correct
27 Correct 2205 ms 26056 KB Output is correct
28 Correct 2128 ms 25808 KB Output is correct
29 Execution timed out 4000 ms 30864 KB
30 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 11556 KB Output is correct
2 Correct 13 ms 11080 KB Output is correct
3 Correct 15 ms 11512 KB Output is correct
4 Correct 15 ms 11272 KB Output is correct
5 Correct 16 ms 11396 KB Output is correct
6 Correct 15 ms 11084 KB Output is correct
7 Correct 32 ms 16380 KB Output is correct
8 Correct 67 ms 13880 KB Output is correct
9 Correct 66 ms 13684 KB Output is correct
10 Correct 56 ms 13532 KB Output is correct
11 Correct 61 ms 13548 KB Output is correct
12 Correct 57 ms 13792 KB Output is correct
13 Correct 63 ms 13660 KB Output is correct
14 Correct 216 ms 24584 KB Output is correct
15 Correct 461 ms 19000 KB Output is correct
16 Correct 445 ms 18992 KB Output is correct
17 Correct 473 ms 18988 KB Output is correct
18 Correct 462 ms 18996 KB Output is correct
19 Correct 465 ms 19116 KB Output is correct
20 Correct 459 ms 19044 KB Output is correct
21 Correct 1067 ms 22076 KB Output is correct
22 Correct 2299 ms 25820 KB Output is correct
23 Correct 2409 ms 25868 KB Output is correct
24 Correct 2300 ms 25980 KB Output is correct
25 Correct 2299 ms 25808 KB Output is correct
26 Correct 2164 ms 25796 KB Output is correct
27 Correct 2205 ms 26056 KB Output is correct
28 Correct 2128 ms 25808 KB Output is correct
29 Execution timed out 4000 ms 30864 KB
30 Halted 0 ms 0 KB -

Subtask #8
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 11556 KB Output is correct
2 Correct 13 ms 11080 KB Output is correct
3 Correct 15 ms 11512 KB Output is correct
4 Correct 15 ms 11272 KB Output is correct
5 Correct 16 ms 11396 KB Output is correct
6 Correct 15 ms 11084 KB Output is correct
7 Correct 32 ms 16380 KB Output is correct
8 Correct 67 ms 13880 KB Output is correct
9 Correct 66 ms 13684 KB Output is correct
10 Correct 56 ms 13532 KB Output is correct
11 Correct 61 ms 13548 KB Output is correct
12 Correct 57 ms 13792 KB Output is correct
13 Correct 63 ms 13660 KB Output is correct
14 Correct 216 ms 24584 KB Output is correct
15 Correct 461 ms 19000 KB Output is correct
16 Correct 445 ms 18992 KB Output is correct
17 Correct 473 ms 18988 KB Output is correct
18 Correct 462 ms 18996 KB Output is correct
19 Correct 465 ms 19116 KB Output is correct
20 Correct 459 ms 19044 KB Output is correct
21 Correct 1067 ms 22076 KB Output is correct
22 Correct 2299 ms 25820 KB Output is correct
23 Correct 2409 ms 25868 KB Output is correct
24 Correct 2300 ms 25980 KB Output is correct
25 Correct 2299 ms 25808 KB Output is correct
26 Correct 2164 ms 25796 KB Output is correct
27 Correct 2205 ms 26056 KB Output is correct
28 Correct 2128 ms 25808 KB Output is correct
29 Execution timed out 4000 ms 30864 KB
30 Halted 0 ms 0 KB -

Subtask #9
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 11556 KB Output is correct
2 Correct 13 ms 11080 KB Output is correct
3 Correct 15 ms 11512 KB Output is correct
4 Correct 15 ms 11272 KB Output is correct
5 Correct 16 ms 11396 KB Output is correct
6 Correct 15 ms 11084 KB Output is correct
7 Correct 32 ms 16380 KB Output is correct
8 Correct 67 ms 13880 KB Output is correct
9 Correct 66 ms 13684 KB Output is correct
10 Correct 56 ms 13532 KB Output is correct
11 Correct 61 ms 13548 KB Output is correct
12 Correct 57 ms 13792 KB Output is correct
13 Correct 63 ms 13660 KB Output is correct
14 Correct 216 ms 24584 KB Output is correct
15 Correct 461 ms 19000 KB Output is correct
16 Correct 445 ms 18992 KB Output is correct
17 Correct 473 ms 18988 KB Output is correct
18 Correct 462 ms 18996 KB Output is correct
19 Correct 465 ms 19116 KB Output is correct
20 Correct 459 ms 19044 KB Output is correct
21 Correct 1067 ms 22076 KB Output is correct
22 Correct 2299 ms 25820 KB Output is correct
23 Correct 2409 ms 25868 KB Output is correct
24 Correct 2300 ms 25980 KB Output is correct
25 Correct 2299 ms 25808 KB Output is correct
26 Correct 2164 ms 25796 KB Output is correct
27 Correct 2205 ms 26056 KB Output is correct
28 Correct 2128 ms 25808 KB Output is correct
29 Execution timed out 4000 ms 30864 KB
30 Halted 0 ms 0 KB -

Subtask #10
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 11556 KB Output is correct
2 Correct 13 ms 11080 KB Output is correct
3 Correct 15 ms 11512 KB Output is correct
4 Correct 15 ms 11272 KB Output is correct
5 Correct 16 ms 11396 KB Output is correct
6 Correct 15 ms 11084 KB Output is correct
7 Correct 32 ms 16380 KB Output is correct
8 Correct 67 ms 13880 KB Output is correct
9 Correct 66 ms 13684 KB Output is correct
10 Correct 56 ms 13532 KB Output is correct
11 Correct 61 ms 13548 KB Output is correct
12 Correct 57 ms 13792 KB Output is correct
13 Correct 63 ms 13660 KB Output is correct
14 Correct 216 ms 24584 KB Output is correct
15 Correct 461 ms 19000 KB Output is correct
16 Correct 445 ms 18992 KB Output is correct
17 Correct 473 ms 18988 KB Output is correct
18 Correct 462 ms 18996 KB Output is correct
19 Correct 465 ms 19116 KB Output is correct
20 Correct 459 ms 19044 KB Output is correct
21 Correct 1067 ms 22076 KB Output is correct
22 Correct 2299 ms 25820 KB Output is correct
23 Correct 2409 ms 25868 KB Output is correct
24 Correct 2300 ms 25980 KB Output is correct
25 Correct 2299 ms 25808 KB Output is correct
26 Correct 2164 ms 25796 KB Output is correct
27 Correct 2205 ms 26056 KB Output is correct
28 Correct 2128 ms 25808 KB Output is correct
29 Execution timed out 4000 ms 30864 KB
30 Halted 0 ms 0 KB -