oj.uz

Submission #787592

# Submission time Handle Problem Language Result Execution time Memory
787592 2023-07-19T10:01:43 Z yeyso Mars (APIO22_mars) C++17
21 / 100
 51 ms 2716 KB 
#include "mars.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> m;
vector<vector<int>> v;
void dfs(int i, int j, int z){
	
	if(!v[i][j] and m[i][j] != 48){
		v[i][j] = z;
		
		if(i < m.size() - 1) dfs(i+1, j, z);
		if(j < m.size() - 1) dfs(i, j+1, z);
		if(i > 0) dfs(i-1, j, z);
		if(j > 0) dfs(i, j-1, z);
	}
}
void comp(int grid){

}
vector<vector<int>> decode(string z, int x){
	for(int i = 0; i < x; i ++){
		
	}

}
string encode(vector<vector<int>> matrix){

}

string process(vector<vector<string>> a, int i, int j, int k, int n){
	/*
	Phase 1 - Each corner stores 1 bit of info
	Phase 2 - Each corner stores 4 bits of info
	Phase 3 - Each corner stores 9 bits of info
	Each corner stores phase ^ 2 bits of info

	Phase 2 - info from 2s are combined into info of 3
	    0   1
	3 0 2 0 1
	0 0 0 0 0
	2 0 2 0 1
	0 0 0 0 0
	1 0 1 0 1

	1 2 1 2 1
	3 4 3 4 3
	1 2 1 2 1
	3 4 3 4 3
	1 2 1 2 1
	*/
	string z(100, '0');
	k += 1;
	int x = 0;
	vector<vector<int>> grid(k+1, vector<int>(k+1, 0));
	for(int r = 0; r < k * k; r ++){
		grid[r / k][r % k + 1] = a[0][2][r];
		grid[r / k + 1][r % k + 1] = a[2][2][r];
		grid[r / k + 1][r % k] = a[2][0][r];
		grid[0][0] = a[0][0][0];
	}
	for(int r = 0; r < grid.size(); r ++){
		for(int c = 0; c < grid[r].size(); c ++){
			//cout << grid[r][c] << " ";
			z[x] = grid[r][c];
			x += 1;

		} //cout << "\n";
	}

	if(k == n){
		vector<vector<int>> grid01(k + 1, vector<int>(k, 0));
		vector<vector<int>> grid10(k, vector<int>(k + 1, 0));
		vector<vector<int>> grid11(k, vector<int>(k, 0));

		for(int r = 0; r < k * k; r ++){
			grid01[r / (k)][r % k] = a[0][1][r];
			grid01[r / (k) + 1][r % k] = a[2][1][r];

			grid10[r / k][r % k] = a[1][0][r];
			grid10[r / k][r % k + 1] = a[1][2][r]; 

			grid11[r / k][r % k] = a[1][1][r];
		}

		vector<vector<int>> matrix(2 * k + 1, vector<int>(2 * k + 1, 0));
		v = matrix;
		for(int r = 0; r < grid.size(); r ++){
			for(int c = 0; c < grid[r].size(); c ++){
				matrix[r * 2][c * 2] = grid[r][c];
			}
		}
		for(int r = 0; r < grid01.size(); r ++){
			for(int c = 0; c < grid01[r].size(); c ++){
				matrix[r * 2][c * 2 + 1] = grid01[r][c];
			}
		}
		for(int r = 0; r < grid10.size(); r ++){
			for(int c = 0; c < grid10[r].size(); c ++){
				matrix[r * 2 + 1][c * 2] = grid10[r][c];
			}
		}
		for(int r = 0; r < grid11.size(); r ++){
			for(int c = 0; c < grid11[r].size(); c ++){
				matrix[r * 2 + 1][c * 2 + 1] = grid11[r][c];
			}
		}
		int zz = 1;
		m = matrix;
		for(int r = 0; r < matrix.size(); r ++){
			for(int c = 0; c < matrix[r].size(); c ++){
				dfs(r, c, zz);
				zz += 1;
				//if(matrix[r][c] == 48) cout << 0 << " ";
				//if(matrix[r][c] == 49) cout << 1 << " ";
				//cout << matrix[r][c] << " ";
			} //cout << "\n";
		}

		set<int> is;
		for(int i = 0; i < v.size(); i ++){
			for(int j = 0; j < v[i].size(); j ++){
				//cout << v[i][j] << " ";
				is.insert(v[i][j]);
			} //cout << "\n";
		}
		z = bitset<100>(is.size() - 1).to_string();
		reverse(z.begin(), z.end());
		return z;
		
	}
	
	//if(k == 2) cout << "\n";
	return z;

	
	
}

/*
g++ -Wall -lm -static -DEVAL -o mars -O2 mars.cpp grader.cpp -std=c++17
1
2
1 1 0 1 1
1 1 0 0 1
1 0 0 1 1
0 0 0 0 0
1 0 1 1 1

1
4
1 1 1 0 1 1 1 1 1
1 0 0 0 1 0 0 1 1
0 0 1 1 1 0 1 1 1
1 0 1 1 1 1 1 1 1
0 0 0 1 0 0 0 1 1
1 1 0 1 0 1 1 1 1
1 1 0 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1

1
1
1 1 0 
1 1 0 
1 0 1 

1 0 1 0 1

*/

Compilation message

mars.cpp: In function 'void dfs(int, int, int)':
mars.cpp:11:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |   if(i < m.size() - 1) dfs(i+1, j, z);
      |      ~~^~~~~~~~~~~~~~
mars.cpp:12:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |   if(j < m.size() - 1) dfs(i, j+1, z);
      |      ~~^~~~~~~~~~~~~~
mars.cpp: In function 'std::vector<std::vector<int> > decode(std::string, int)':
mars.cpp:25:1: warning: no return statement in function returning non-void [-Wreturn-type]
   25 | }
      | ^
mars.cpp: In function 'std::string encode(std::vector<std::vector<int> >)':
mars.cpp:28:1: warning: no return statement in function returning non-void [-Wreturn-type]
   28 | }
      | ^
mars.cpp: In function 'std::string process(std::vector<std::vector<std::__cxx11::basic_string<char> > >, int, int, int, int)':
mars.cpp:61:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for(int r = 0; r < grid.size(); r ++){
      |                 ~~^~~~~~~~~~~~~
mars.cpp:62:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |   for(int c = 0; c < grid[r].size(); c ++){
      |                  ~~^~~~~~~~~~~~~~~~
mars.cpp:87:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |   for(int r = 0; r < grid.size(); r ++){
      |                  ~~^~~~~~~~~~~~~
mars.cpp:88:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |    for(int c = 0; c < grid[r].size(); c ++){
      |                   ~~^~~~~~~~~~~~~~~~
mars.cpp:92:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |   for(int r = 0; r < grid01.size(); r ++){
      |                  ~~^~~~~~~~~~~~~~~
mars.cpp:93:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |    for(int c = 0; c < grid01[r].size(); c ++){
      |                   ~~^~~~~~~~~~~~~~~~~~
mars.cpp:97:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |   for(int r = 0; r < grid10.size(); r ++){
      |                  ~~^~~~~~~~~~~~~~~
mars.cpp:98:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |    for(int c = 0; c < grid10[r].size(); c ++){
      |                   ~~^~~~~~~~~~~~~~~~~~
mars.cpp:102:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |   for(int r = 0; r < grid11.size(); r ++){
      |                  ~~^~~~~~~~~~~~~~~
mars.cpp:103:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |    for(int c = 0; c < grid11[r].size(); c ++){
      |                   ~~^~~~~~~~~~~~~~~~~~
mars.cpp:109:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |   for(int r = 0; r < matrix.size(); r ++){
      |                  ~~^~~~~~~~~~~~~~~
mars.cpp:110:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |    for(int c = 0; c < matrix[r].size(); c ++){
      |                   ~~^~~~~~~~~~~~~~~~~~
mars.cpp:120:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |   for(int i = 0; i < v.size(); i ++){
      |                  ~~^~~~~~~~~~
mars.cpp:121:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |    for(int j = 0; j < v[i].size(); j ++){
      |                   ~~^~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2272 KB Output is correct
2 Correct 3 ms 2060 KB Output is correct
3 Correct 4 ms 2232 KB Output is correct
4 Correct 3 ms 1952 KB Output is correct
5 Correct 5 ms 1944 KB Output is correct
6 Correct 3 ms 2124 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2272 KB Output is correct
2 Correct 3 ms 2060 KB Output is correct
3 Correct 4 ms 2232 KB Output is correct
4 Correct 3 ms 1952 KB Output is correct
5 Correct 5 ms 1944 KB Output is correct
6 Correct 3 ms 2124 KB Output is correct
7 Correct 8 ms 1884 KB Output is correct
8 Correct 8 ms 1600 KB Output is correct
9 Correct 9 ms 2072 KB Output is correct
10 Correct 9 ms 2008 KB Output is correct
11 Correct 8 ms 1904 KB Output is correct
12 Correct 9 ms 1768 KB Output is correct
13 Correct 8 ms 2164 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2272 KB Output is correct
2 Correct 3 ms 2060 KB Output is correct
3 Correct 4 ms 2232 KB Output is correct
4 Correct 3 ms 1952 KB Output is correct
5 Correct 5 ms 1944 KB Output is correct
6 Correct 3 ms 2124 KB Output is correct
7 Correct 8 ms 1884 KB Output is correct
8 Correct 8 ms 1600 KB Output is correct
9 Correct 9 ms 2072 KB Output is correct
10 Correct 9 ms 2008 KB Output is correct
11 Correct 8 ms 1904 KB Output is correct
12 Correct 9 ms 1768 KB Output is correct
13 Correct 8 ms 2164 KB Output is correct
14 Correct 17 ms 2532 KB Output is correct
15 Correct 23 ms 2576 KB Output is correct
16 Correct 23 ms 2588 KB Output is correct
17 Correct 26 ms 2564 KB Output is correct
18 Correct 24 ms 2564 KB Output is correct
19 Correct 22 ms 2568 KB Output is correct
20 Correct 23 ms 2556 KB Output is correct

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2272 KB Output is correct
2 Correct 3 ms 2060 KB Output is correct
3 Correct 4 ms 2232 KB Output is correct
4 Correct 3 ms 1952 KB Output is correct
5 Correct 5 ms 1944 KB Output is correct
6 Correct 3 ms 2124 KB Output is correct
7 Correct 8 ms 1884 KB Output is correct
8 Correct 8 ms 1600 KB Output is correct
9 Correct 9 ms 2072 KB Output is correct
10 Correct 9 ms 2008 KB Output is correct
11 Correct 8 ms 1904 KB Output is correct
12 Correct 9 ms 1768 KB Output is correct
13 Correct 8 ms 2164 KB Output is correct
14 Correct 17 ms 2532 KB Output is correct
15 Correct 23 ms 2576 KB Output is correct
16 Correct 23 ms 2588 KB Output is correct
17 Correct 26 ms 2564 KB Output is correct
18 Correct 24 ms 2564 KB Output is correct
19 Correct 22 ms 2568 KB Output is correct
20 Correct 23 ms 2556 KB Output is correct
21 Correct 35 ms 2608 KB Output is correct
22 Correct 51 ms 2716 KB Output is correct
23 Correct 46 ms 2664 KB Output is correct
24 Correct 49 ms 2680 KB Output is correct
25 Incorrect 6 ms 336 KB Incorrect
26 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2272 KB Output is correct
2 Correct 3 ms 2060 KB Output is correct
3 Correct 4 ms 2232 KB Output is correct
4 Correct 3 ms 1952 KB Output is correct
5 Correct 5 ms 1944 KB Output is correct
6 Correct 3 ms 2124 KB Output is correct
7 Correct 8 ms 1884 KB Output is correct
8 Correct 8 ms 1600 KB Output is correct
9 Correct 9 ms 2072 KB Output is correct
10 Correct 9 ms 2008 KB Output is correct
11 Correct 8 ms 1904 KB Output is correct
12 Correct 9 ms 1768 KB Output is correct
13 Correct 8 ms 2164 KB Output is correct
14 Correct 17 ms 2532 KB Output is correct
15 Correct 23 ms 2576 KB Output is correct
16 Correct 23 ms 2588 KB Output is correct
17 Correct 26 ms 2564 KB Output is correct
18 Correct 24 ms 2564 KB Output is correct
19 Correct 22 ms 2568 KB Output is correct
20 Correct 23 ms 2556 KB Output is correct
21 Correct 35 ms 2608 KB Output is correct
22 Correct 51 ms 2716 KB Output is correct
23 Correct 46 ms 2664 KB Output is correct
24 Correct 49 ms 2680 KB Output is correct
25 Incorrect 6 ms 336 KB Incorrect
26 Halted 0 ms 0 KB -

Subtask #6
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2272 KB Output is correct
2 Correct 3 ms 2060 KB Output is correct
3 Correct 4 ms 2232 KB Output is correct
4 Correct 3 ms 1952 KB Output is correct
5 Correct 5 ms 1944 KB Output is correct
6 Correct 3 ms 2124 KB Output is correct
7 Correct 8 ms 1884 KB Output is correct
8 Correct 8 ms 1600 KB Output is correct
9 Correct 9 ms 2072 KB Output is correct
10 Correct 9 ms 2008 KB Output is correct
11 Correct 8 ms 1904 KB Output is correct
12 Correct 9 ms 1768 KB Output is correct
13 Correct 8 ms 2164 KB Output is correct
14 Correct 17 ms 2532 KB Output is correct
15 Correct 23 ms 2576 KB Output is correct
16 Correct 23 ms 2588 KB Output is correct
17 Correct 26 ms 2564 KB Output is correct
18 Correct 24 ms 2564 KB Output is correct
19 Correct 22 ms 2568 KB Output is correct
20 Correct 23 ms 2556 KB Output is correct
21 Correct 35 ms 2608 KB Output is correct
22 Correct 51 ms 2716 KB Output is correct
23 Correct 46 ms 2664 KB Output is correct
24 Correct 49 ms 2680 KB Output is correct
25 Incorrect 6 ms 336 KB Incorrect
26 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2272 KB Output is correct
2 Correct 3 ms 2060 KB Output is correct
3 Correct 4 ms 2232 KB Output is correct
4 Correct 3 ms 1952 KB Output is correct
5 Correct 5 ms 1944 KB Output is correct
6 Correct 3 ms 2124 KB Output is correct
7 Correct 8 ms 1884 KB Output is correct
8 Correct 8 ms 1600 KB Output is correct
9 Correct 9 ms 2072 KB Output is correct
10 Correct 9 ms 2008 KB Output is correct
11 Correct 8 ms 1904 KB Output is correct
12 Correct 9 ms 1768 KB Output is correct
13 Correct 8 ms 2164 KB Output is correct
14 Correct 17 ms 2532 KB Output is correct
15 Correct 23 ms 2576 KB Output is correct
16 Correct 23 ms 2588 KB Output is correct
17 Correct 26 ms 2564 KB Output is correct
18 Correct 24 ms 2564 KB Output is correct
19 Correct 22 ms 2568 KB Output is correct
20 Correct 23 ms 2556 KB Output is correct
21 Correct 35 ms 2608 KB Output is correct
22 Correct 51 ms 2716 KB Output is correct
23 Correct 46 ms 2664 KB Output is correct
24 Correct 49 ms 2680 KB Output is correct
25 Incorrect 6 ms 336 KB Incorrect
26 Halted 0 ms 0 KB -

Subtask #8
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2272 KB Output is correct
2 Correct 3 ms 2060 KB Output is correct
3 Correct 4 ms 2232 KB Output is correct
4 Correct 3 ms 1952 KB Output is correct
5 Correct 5 ms 1944 KB Output is correct
6 Correct 3 ms 2124 KB Output is correct
7 Correct 8 ms 1884 KB Output is correct
8 Correct 8 ms 1600 KB Output is correct
9 Correct 9 ms 2072 KB Output is correct
10 Correct 9 ms 2008 KB Output is correct
11 Correct 8 ms 1904 KB Output is correct
12 Correct 9 ms 1768 KB Output is correct
13 Correct 8 ms 2164 KB Output is correct
14 Correct 17 ms 2532 KB Output is correct
15 Correct 23 ms 2576 KB Output is correct
16 Correct 23 ms 2588 KB Output is correct
17 Correct 26 ms 2564 KB Output is correct
18 Correct 24 ms 2564 KB Output is correct
19 Correct 22 ms 2568 KB Output is correct
20 Correct 23 ms 2556 KB Output is correct
21 Correct 35 ms 2608 KB Output is correct
22 Correct 51 ms 2716 KB Output is correct
23 Correct 46 ms 2664 KB Output is correct
24 Correct 49 ms 2680 KB Output is correct
25 Incorrect 6 ms 336 KB Incorrect
26 Halted 0 ms 0 KB -

Subtask #9
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2272 KB Output is correct
2 Correct 3 ms 2060 KB Output is correct
3 Correct 4 ms 2232 KB Output is correct
4 Correct 3 ms 1952 KB Output is correct
5 Correct 5 ms 1944 KB Output is correct
6 Correct 3 ms 2124 KB Output is correct
7 Correct 8 ms 1884 KB Output is correct
8 Correct 8 ms 1600 KB Output is correct
9 Correct 9 ms 2072 KB Output is correct
10 Correct 9 ms 2008 KB Output is correct
11 Correct 8 ms 1904 KB Output is correct
12 Correct 9 ms 1768 KB Output is correct
13 Correct 8 ms 2164 KB Output is correct
14 Correct 17 ms 2532 KB Output is correct
15 Correct 23 ms 2576 KB Output is correct
16 Correct 23 ms 2588 KB Output is correct
17 Correct 26 ms 2564 KB Output is correct
18 Correct 24 ms 2564 KB Output is correct
19 Correct 22 ms 2568 KB Output is correct
20 Correct 23 ms 2556 KB Output is correct
21 Correct 35 ms 2608 KB Output is correct
22 Correct 51 ms 2716 KB Output is correct
23 Correct 46 ms 2664 KB Output is correct
24 Correct 49 ms 2680 KB Output is correct
25 Incorrect 6 ms 336 KB Incorrect
26 Halted 0 ms 0 KB -

Subtask #10
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2272 KB Output is correct
2 Correct 3 ms 2060 KB Output is correct
3 Correct 4 ms 2232 KB Output is correct
4 Correct 3 ms 1952 KB Output is correct
5 Correct 5 ms 1944 KB Output is correct
6 Correct 3 ms 2124 KB Output is correct
7 Correct 8 ms 1884 KB Output is correct
8 Correct 8 ms 1600 KB Output is correct
9 Correct 9 ms 2072 KB Output is correct
10 Correct 9 ms 2008 KB Output is correct
11 Correct 8 ms 1904 KB Output is correct
12 Correct 9 ms 1768 KB Output is correct
13 Correct 8 ms 2164 KB Output is correct
14 Correct 17 ms 2532 KB Output is correct
15 Correct 23 ms 2576 KB Output is correct
16 Correct 23 ms 2588 KB Output is correct
17 Correct 26 ms 2564 KB Output is correct
18 Correct 24 ms 2564 KB Output is correct
19 Correct 22 ms 2568 KB Output is correct
20 Correct 23 ms 2556 KB Output is correct
21 Correct 35 ms 2608 KB Output is correct
22 Correct 51 ms 2716 KB Output is correct
23 Correct 46 ms 2664 KB Output is correct
24 Correct 49 ms 2680 KB Output is correct
25 Incorrect 6 ms 336 KB Incorrect
26 Halted 0 ms 0 KB -