Submission #787607

#	Time	Username	Problem	Language	Result	Execution time	Memory
787607		yeyso	Mars (APIO22_mars)	C++17	36 / 100	107 ms	2868 KiB

mars

#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];
		}
		if(k != n){
			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;
		cout << "\n";
		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";
		}
		if(is.size() - 1 == 0 and v[0][0] != 0){
			z = bitset<100>(is.size()).to_string();
		} else {
			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
8
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 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 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 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 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 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 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 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 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 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 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 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 (stderr)

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:64:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |    for(int r = 0; r < grid.size(); r ++){
      |                   ~~^~~~~~~~~~~~~
mars.cpp:65:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     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 < grid.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 < grid[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 < grid01.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 < grid01[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 < grid10.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 < grid10[r].size(); c ++){
      |                   ~~^~~~~~~~~~~~~~~~~~
mars.cpp:107:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |   for(int r = 0; r < grid11.size(); r ++){
      |                  ~~^~~~~~~~~~~~~~~
mars.cpp:108:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |    for(int c = 0; c < grid11[r].size(); c ++){
      |                   ~~^~~~~~~~~~~~~~~~~~
mars.cpp:115:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |   for(int r = 0; r < matrix.size(); r ++){
      |                  ~~^~~~~~~~~~~~~~~
mars.cpp:116:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |    for(int c = 0; c < matrix[r].size(); c ++){
      |                   ~~^~~~~~~~~~~~~~~~~~
mars.cpp:126:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |   for(int i = 0; i < v.size(); i ++){
      |                  ~~^~~~~~~~~~
mars.cpp:127:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |    for(int j = 0; j < v[i].size(); j ++){
      |                   ~~^~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 7 / 7
• Subtask 4: 8 / 8
• Subtask 5: 7 / 7
• Subtask 6: 0 / 8
• Subtask 7: 0 / 10
• Subtask 8: 0 / 24
• Subtask 9: 0 / 11
• Subtask 10: 0 / 11