oj.uz

Submission #969842

# Submission time Handle Problem Language Result Execution time Memory
969842 2024-04-25T16:40:25 Z anton Mars (APIO22_mars) C++17
21 / 100
 36 ms 4748 KB 
#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

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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4004 KB Output is correct
2 Correct 6 ms 4192 KB Output is correct
3 Correct 5 ms 4224 KB Output is correct
4 Correct 7 ms 4444 KB Output is correct
5 Correct 4 ms 4192 KB Output is correct
6 Correct 4 ms 4092 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4004 KB Output is correct
2 Correct 6 ms 4192 KB Output is correct
3 Correct 5 ms 4224 KB Output is correct
4 Correct 7 ms 4444 KB Output is correct
5 Correct 4 ms 4192 KB Output is correct
6 Correct 4 ms 4092 KB Output is correct
7 Correct 8 ms 3944 KB Output is correct
8 Correct 9 ms 3868 KB Output is correct
9 Correct 12 ms 4148 KB Output is correct
10 Correct 11 ms 4096 KB Output is correct
11 Correct 8 ms 3840 KB Output is correct
12 Correct 8 ms 3612 KB Output is correct
13 Correct 9 ms 3976 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4004 KB Output is correct
2 Correct 6 ms 4192 KB Output is correct
3 Correct 5 ms 4224 KB Output is correct
4 Correct 7 ms 4444 KB Output is correct
5 Correct 4 ms 4192 KB Output is correct
6 Correct 4 ms 4092 KB Output is correct
7 Correct 8 ms 3944 KB Output is correct
8 Correct 9 ms 3868 KB Output is correct
9 Correct 12 ms 4148 KB Output is correct
10 Correct 11 ms 4096 KB Output is correct
11 Correct 8 ms 3840 KB Output is correct
12 Correct 8 ms 3612 KB Output is correct
13 Correct 9 ms 3976 KB Output is correct
14 Correct 19 ms 4252 KB Output is correct
15 Correct 24 ms 4132 KB Output is correct
16 Correct 27 ms 3912 KB Output is correct
17 Correct 23 ms 4312 KB Output is correct
18 Correct 23 ms 4748 KB Output is correct
19 Correct 27 ms 4472 KB Output is correct
20 Correct 24 ms 4340 KB Output is correct

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4004 KB Output is correct
2 Correct 6 ms 4192 KB Output is correct
3 Correct 5 ms 4224 KB Output is correct
4 Correct 7 ms 4444 KB Output is correct
5 Correct 4 ms 4192 KB Output is correct
6 Correct 4 ms 4092 KB Output is correct
7 Correct 8 ms 3944 KB Output is correct
8 Correct 9 ms 3868 KB Output is correct
9 Correct 12 ms 4148 KB Output is correct
10 Correct 11 ms 4096 KB Output is correct
11 Correct 8 ms 3840 KB Output is correct
12 Correct 8 ms 3612 KB Output is correct
13 Correct 9 ms 3976 KB Output is correct
14 Correct 19 ms 4252 KB Output is correct
15 Correct 24 ms 4132 KB Output is correct
16 Correct 27 ms 3912 KB Output is correct
17 Correct 23 ms 4312 KB Output is correct
18 Correct 23 ms 4748 KB Output is correct
19 Correct 27 ms 4472 KB Output is correct
20 Correct 24 ms 4340 KB Output is correct
21 Correct 36 ms 4288 KB Output is correct
22 Incorrect 7 ms 484 KB invalid len
23 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4004 KB Output is correct
2 Correct 6 ms 4192 KB Output is correct
3 Correct 5 ms 4224 KB Output is correct
4 Correct 7 ms 4444 KB Output is correct
5 Correct 4 ms 4192 KB Output is correct
6 Correct 4 ms 4092 KB Output is correct
7 Correct 8 ms 3944 KB Output is correct
8 Correct 9 ms 3868 KB Output is correct
9 Correct 12 ms 4148 KB Output is correct
10 Correct 11 ms 4096 KB Output is correct
11 Correct 8 ms 3840 KB Output is correct
12 Correct 8 ms 3612 KB Output is correct
13 Correct 9 ms 3976 KB Output is correct
14 Correct 19 ms 4252 KB Output is correct
15 Correct 24 ms 4132 KB Output is correct
16 Correct 27 ms 3912 KB Output is correct
17 Correct 23 ms 4312 KB Output is correct
18 Correct 23 ms 4748 KB Output is correct
19 Correct 27 ms 4472 KB Output is correct
20 Correct 24 ms 4340 KB Output is correct
21 Correct 36 ms 4288 KB Output is correct
22 Incorrect 7 ms 484 KB invalid len
23 Halted 0 ms 0 KB -

Subtask #6
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4004 KB Output is correct
2 Correct 6 ms 4192 KB Output is correct
3 Correct 5 ms 4224 KB Output is correct
4 Correct 7 ms 4444 KB Output is correct
5 Correct 4 ms 4192 KB Output is correct
6 Correct 4 ms 4092 KB Output is correct
7 Correct 8 ms 3944 KB Output is correct
8 Correct 9 ms 3868 KB Output is correct
9 Correct 12 ms 4148 KB Output is correct
10 Correct 11 ms 4096 KB Output is correct
11 Correct 8 ms 3840 KB Output is correct
12 Correct 8 ms 3612 KB Output is correct
13 Correct 9 ms 3976 KB Output is correct
14 Correct 19 ms 4252 KB Output is correct
15 Correct 24 ms 4132 KB Output is correct
16 Correct 27 ms 3912 KB Output is correct
17 Correct 23 ms 4312 KB Output is correct
18 Correct 23 ms 4748 KB Output is correct
19 Correct 27 ms 4472 KB Output is correct
20 Correct 24 ms 4340 KB Output is correct
21 Correct 36 ms 4288 KB Output is correct
22 Incorrect 7 ms 484 KB invalid len
23 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4004 KB Output is correct
2 Correct 6 ms 4192 KB Output is correct
3 Correct 5 ms 4224 KB Output is correct
4 Correct 7 ms 4444 KB Output is correct
5 Correct 4 ms 4192 KB Output is correct
6 Correct 4 ms 4092 KB Output is correct
7 Correct 8 ms 3944 KB Output is correct
8 Correct 9 ms 3868 KB Output is correct
9 Correct 12 ms 4148 KB Output is correct
10 Correct 11 ms 4096 KB Output is correct
11 Correct 8 ms 3840 KB Output is correct
12 Correct 8 ms 3612 KB Output is correct
13 Correct 9 ms 3976 KB Output is correct
14 Correct 19 ms 4252 KB Output is correct
15 Correct 24 ms 4132 KB Output is correct
16 Correct 27 ms 3912 KB Output is correct
17 Correct 23 ms 4312 KB Output is correct
18 Correct 23 ms 4748 KB Output is correct
19 Correct 27 ms 4472 KB Output is correct
20 Correct 24 ms 4340 KB Output is correct
21 Correct 36 ms 4288 KB Output is correct
22 Incorrect 7 ms 484 KB invalid len
23 Halted 0 ms 0 KB -

Subtask #8
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4004 KB Output is correct
2 Correct 6 ms 4192 KB Output is correct
3 Correct 5 ms 4224 KB Output is correct
4 Correct 7 ms 4444 KB Output is correct
5 Correct 4 ms 4192 KB Output is correct
6 Correct 4 ms 4092 KB Output is correct
7 Correct 8 ms 3944 KB Output is correct
8 Correct 9 ms 3868 KB Output is correct
9 Correct 12 ms 4148 KB Output is correct
10 Correct 11 ms 4096 KB Output is correct
11 Correct 8 ms 3840 KB Output is correct
12 Correct 8 ms 3612 KB Output is correct
13 Correct 9 ms 3976 KB Output is correct
14 Correct 19 ms 4252 KB Output is correct
15 Correct 24 ms 4132 KB Output is correct
16 Correct 27 ms 3912 KB Output is correct
17 Correct 23 ms 4312 KB Output is correct
18 Correct 23 ms 4748 KB Output is correct
19 Correct 27 ms 4472 KB Output is correct
20 Correct 24 ms 4340 KB Output is correct
21 Correct 36 ms 4288 KB Output is correct
22 Incorrect 7 ms 484 KB invalid len
23 Halted 0 ms 0 KB -

Subtask #9
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4004 KB Output is correct
2 Correct 6 ms 4192 KB Output is correct
3 Correct 5 ms 4224 KB Output is correct
4 Correct 7 ms 4444 KB Output is correct
5 Correct 4 ms 4192 KB Output is correct
6 Correct 4 ms 4092 KB Output is correct
7 Correct 8 ms 3944 KB Output is correct
8 Correct 9 ms 3868 KB Output is correct
9 Correct 12 ms 4148 KB Output is correct
10 Correct 11 ms 4096 KB Output is correct
11 Correct 8 ms 3840 KB Output is correct
12 Correct 8 ms 3612 KB Output is correct
13 Correct 9 ms 3976 KB Output is correct
14 Correct 19 ms 4252 KB Output is correct
15 Correct 24 ms 4132 KB Output is correct
16 Correct 27 ms 3912 KB Output is correct
17 Correct 23 ms 4312 KB Output is correct
18 Correct 23 ms 4748 KB Output is correct
19 Correct 27 ms 4472 KB Output is correct
20 Correct 24 ms 4340 KB Output is correct
21 Correct 36 ms 4288 KB Output is correct
22 Incorrect 7 ms 484 KB invalid len
23 Halted 0 ms 0 KB -

Subtask #10
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4004 KB Output is correct
2 Correct 6 ms 4192 KB Output is correct
3 Correct 5 ms 4224 KB Output is correct
4 Correct 7 ms 4444 KB Output is correct
5 Correct 4 ms 4192 KB Output is correct
6 Correct 4 ms 4092 KB Output is correct
7 Correct 8 ms 3944 KB Output is correct
8 Correct 9 ms 3868 KB Output is correct
9 Correct 12 ms 4148 KB Output is correct
10 Correct 11 ms 4096 KB Output is correct
11 Correct 8 ms 3840 KB Output is correct
12 Correct 8 ms 3612 KB Output is correct
13 Correct 9 ms 3976 KB Output is correct
14 Correct 19 ms 4252 KB Output is correct
15 Correct 24 ms 4132 KB Output is correct
16 Correct 27 ms 3912 KB Output is correct
17 Correct 23 ms 4312 KB Output is correct
18 Correct 23 ms 4748 KB Output is correct
19 Correct 27 ms 4472 KB Output is correct
20 Correct 24 ms 4340 KB Output is correct
21 Correct 36 ms 4288 KB Output is correct
22 Incorrect 7 ms 484 KB invalid len
23 Halted 0 ms 0 KB -