Submission #969842

#	Time	Username	Problem	Language	Result	Execution time	Memory
969842		anton	Mars (APIO22_mars)	C++17	21 / 100	36 ms	4748 KiB

mars

#include "mars.h"
#include<bits/stdc++.h>

using namespace std;
#define pii pair<int, int>
#define x real()
#define y imag()
#define point complex<int>


int to_id(int i, int j, int sz){
	return i*sz + j;
}

int geometric(int n){
    return (n*(n+1))/2;
}

int get_sz(int i, int j, int k, int n){
    //cout<<"sz "<<i<<" "<<j<<" "<<k<<endl;
    if(i< 2*(n-k-1) && j <2*(n-k-1)){
        return 1;
    }
    if(k <0){
        return 1;
    }
    if(i<2 && j<2){
        return 1;
    }
    if(i == 0){
        if(j%2 == 1){
            return 1;
        }
        return geometric((2*n)+1 - j);
    }
    else if( j==0){
        if(i%2 == 1){
            return 1;
        }
        return geometric((2*n)+1-i);
    }
    else{
        if(i>=j && i%2 == 1){
            return 1;
        }
        if(j>=i && j%2 ==1){
            return 1;
        }
        //cout<<(2*n)<<" "<<1-j<<endl;
       //cout<<min((2*n)+1-j, (2*n)+1-i)<<endl;
        return min((2*n)+1-j, (2*n)+1-i);
    }
}

void append(vector<int>& v, vector<int>& b){
    for(auto e: b){
        v.push_back(e);
    }
}

vector<int> to_vec(string s, int i, int j, int n, int k){
    vector<int> res;
    for(int l =0; l<get_sz(i, j,k,n); l++){
        res.push_back(s[l]-'0');
    }
    return res;
}
string to_string(vector<int> v){
    string res;
    for(auto e:v){
        res.push_back(e + '0');
    }
    while(res.size()<100){
        res.push_back('0');
    }
    return res;
}

vector<vector<vector<int>>> a_to_vec(vector<vector<string>> a, int _i, int _j, int n, int k){
    vector<vector<vector<int>>> res(3, vector<vector<int>>(3));
    for(int i = 0;i<3; i++){
        for(int j = 0; j<3; j++){
            //cout<<"pos "<<i+_i<<" "<<j+_j<<endl;
            //cout<<"n: "<<n<<endl;
            //cout<<"sz: "<<get_sz(i+_i, j+_j, k, n)<<endl;
            //cout<<a[i][j]<<endl;
            res[i][j] =  to_vec(a[i][j],i+_i,j+_j,n, k-1);
            /*for(auto e: res[i][j]){
                cout<<e<<" ";
            }
            cout<<endl;*/
        }
    }
    return res;
}

vector<int> merge_left(vector<vector<vector<int>>>& a){
    vector<int> res;
    for(int i = 0; i<3; i++){
        for(int j = 0; j<=i; j++){
            append(res, a[i][j]);
        }
    }
    return res;
}
vector<int> merge_right(vector<vector<vector<int>>>& a){
    vector<int> res;
    for(int i = 0; i<3; i++){
        for(int j = i; j<3; j++){
            //cout<<"inc "<<i<<" "<<j<<" "<<a[i][j].size()<<endl;
            append(res, a[i][j]);

        }
    }
    return res;
}

vector<int> merge_diag(vector<vector<vector<int>>>& a){
    vector<int> res;
    for(int i = 0; i<3; i++){
        append(res, a[i][i]);

    }
    return res;
}
void dfs(vector<vector<char>>&r, point pos, vector<vector<bool>>& vis, int h){
	vis[pos.x][pos.y] = true;
	
	vector<point> d = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
	for(auto e: d){
		point np = pos + e;
		if(np.x>=0 && np.x<h){
			if(np.y>=0 && np.y<h){
				if(!vis[np.x][np.y]){
					if(r[np.x][np.y] == '1'){
						dfs(r, np, vis, h);
					}
				}
			}
		}
	}
}

int count_components(vector<vector<char>> r, int k){
	
	int h = (2*k+3);
	vector<vector<bool>> vis(h, vector<bool>(h));

	
	int res=  0;
	for(int i = 0; i<h; i++){
		for(int j = 0; j<h; j++){
			if(!vis[i][j]){
				if(r[i][j] == '1'){
					res++;
					dfs(r, {i, j}, vis, h);
				}
			}
		}
	}
	return res;
}



string to_str(int v){
	string res(100, '0');
	for(int i = 0; i<20; i++){
		if(v & (1<<i)){
			res[i] = '1';
		}
	}
	return res;
}


vector<int> process_edge(vector<vector<vector<int>>> a, int i, int j, int k){
    if(j==0){
        return merge_left(a);
    }
    else{
        if(i==0){
            return merge_right(a);
        }
        else{
            return merge_diag(a);
        }
    }
}

vector<vector<vector<int>>> simulate(int n){
    int sz = 2*n+1;
    vector<vector<vector<int>>> content(sz, vector<vector<int>>(sz));
    for(int i = 0; i<sz; i++){
        for(int j = 0; j<sz; j++){
            content[i][j].push_back(i*sz + j);
            //cout<<i<<" "<<j<<" "<<i*sz+j<<endl;
        }
    }

    for(int k = 0; k<n-1; k++){
        for(int i = 0; i<=2*(n-k-1); i++){
            for(int j = 0; j<=2*(n-k-1); j++){
                if(i == 2*(n-k-1) || j == 2*(n-k-1)){
                    vector<vector<vector<int>>>a (3, vector<vector<int>>(3));
                    for(int h= 0; h<3; h++){
                        for(int l = 0; l<3; l++){
                            a[h][l] = content[i+h][j+l];
                        }
                    }
                    content[i][j]= process_edge(a, i, j, k);
                }
            }
        }
    }

    return content;
}

vector<vector<char>> get_final(vector<vector<vector<int>>> a, int n){
    vector<vector<vector<int>>> final_pos = simulate(n);
    vector<vector<char>> m(2*n+1, vector<char>(2*n+1, '0'));
    int sz = 2*n+1;
    for(int i = 0; i<3; i++){
        for(int j = 0; j<3; j++){
            if(final_pos[i][j].size() != a[i][j].size()){
                //cout<<"error "<<i<<" "<<j<<" "<<final_pos[i][j].size()<<" "<<a[i][j].size()<<endl;
            }
            for(int k = 0;k<final_pos[i][j].size(); k++){
                auto e = final_pos[i][j][k];
                m[e/sz][e%sz] = a[i][j][k] + '0';
            }
        }
    }

    return m;
}
std::string process(std::vector <std::vector<std::string>> a, int i, int j, int k, int n)
{
	/*simulate(n);
    return string(101, '0');*/
	
    if(k ==n-1){
        return to_str(count_components(get_final(a_to_vec(a, i, j, n, k), n), k));
    }
    else{
        if(i == 2*(n-k-1) || j == 2*(n-k-1)){
            vector<int> res =process_edge(a_to_vec(a, i, j, n, k), i, j, k);
            return to_string(res);
        }
        else{
            return a[0][0];
        }
    }
}	
	

Compilation message (stderr)

mars.cpp: In function 'std::vector<std::vector<char> > get_final(std::vector<std::vector<std::vector<int> > >, int)':
mars.cpp:229:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  229 |             for(int k = 0;k<final_pos[i][j].size(); k++){
      |                           ~^~~~~~~~~~~~~~~~~~~~~~~

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