Submission #593326

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
593326	2022-07-10T21:31:05 Z	CSQ31	Mars (APIO22_mars)	C++17	29 / 100	110 ms	2832 KB

mars

#include "mars.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define INF (int)(1e9+1)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
//at phase 4 we make everything a map of 10x10
//phase 5 shift diagonal 
//phase 6
//phase 7
//phase 8
//phase 9
//phase 10
int iii;
string process(vector <vector<string>> a, int I, int J, int k, int n)
{
	iii=J;
	string ans(100,'0');
	if(k!=n-1){ 
		if(k<4){ //make 10 x 10
			int s = 2*k+1;
			int f = 2*k+3;
			vii g(40,vector<int>(40));
			for(int i=0;i<3;i++){
				for(int j=0;j<3;j++){
					for(int k=0;k<s*s;k++){
						g[k/s+i][k%s+j] = a[i][j][k] - '0';
						
					}	
				}
			}
			for(int k=0;k<f*f;k++)ans[k] = '0' + g[k/f][k%f];
		}else{
			ans = a[0][0];
			if(!I && !J)ans = a[0][0];
			else if(I==J){
				if(k>=7 && I==1)ans = a[0][0];
				else ans = a[2][2];
			}
			else if(!I){
				if(k>=7 && J==1)ans = a[0][0];
				else ans = a[0][2];
				
			}
		    else if(!J){
				if(k>=7 && I==1)ans = a[0][0];
				else ans = a[2][0];
			}
			else if(n==10){
				if(I==7 && J==5)ans = a[2][2];
				if(I==5 && J==3)ans = a[2][2];
				if(I==4 && J==3)ans = a[1][0];
				if(I==2 && J==1)ans = a[2][1];
				
				if(I==5 && J==7)ans = a[2][2];
				if(I==3 && J==5)ans = a[2][2];
				if(I==3 && J==4)ans = a[1][0];
				if(I==1 && J==2)ans = a[1][2];
			}
		}
	}
	if(k == n-1){
		vii g(40,vector<int>(40,0));
		if(n<=5){
			int s = 2*n-1;
			for(int i=0;i<3;i++){
				for(int j=0;j<3;j++){
					for(int k=0;k<s*s;k++){
						g[k/s+i][k%s+j] = a[i][j][k] - '0';
						
					}	
				}
			}
		}
		else if(n<=8){
			int s = 9;
			int sh = (n-5)*2;
			for(int i=0;i<3;i++){
				for(int j=0;j<3;j++){
					for(int k=0;k<s*s;k++){
						int ii = i+sh;
						int jj = j+sh;
						if(!i && !j)g[k/s][k%s] = a[i][j][k] - '0';
						else if(i==j)g[k/s + ii][k%s + jj] = a[i][j][k] - '0';
						else if(!i)g[k/s][k%s + jj] = a[i][j][k] - '0';
						else if(!j)g[k/s + ii][k%s] = a[i][j][k] - '0';
						else if(n==10){
						}
						
					}	
				}
			}	
		}
		else if(n<=10){
			int s = 9;
			int sh = (n-5)*2;
			for(int i=0;i<3;i++){
				for(int j=0;j<3;j++){
					for(int k=0;k<s*s;k++){
						int ii = i+sh;
						int jj = j+sh;
						if(!i && !j)g[k/s][k%s] = a[i][j][k] - '0';
						else if(i==j){
							if(i==2)g[k/s + ii][k%s + jj] = a[i][j][k] - '0';
							if(i==1)g[k/s + ii-4][k%s + jj-4] = a[i][j][k] - '0';
						}
						else if(!i){
							if(j==2)g[k/s][k%s + jj] = a[i][j][k] - '0';
							if(j==1)g[k/s][k%s + jj-4] = a[i][j][k] - '0';
						}
						else if(!j){
							if(i==2)g[k/s + ii][k%s] = a[i][j][k] - '0';
							if(i==1)g[k/s + ii-4][k%s] = a[i][j][k] - '0';
						}else if(j==1){
							g[k/s+11][k%s+9] = a[i][j][k] - '0';
							
						}else if(i==1){
							g[k/s+9][k%s+11] = a[i][j][k] - '0';
						}
						
					}	
				}
			}	
		}
		n = 2*n+1;
		bool debug = 0;
		if(debug){
			cout<<'\n';
			for(int i=0;i<n;i++){
				for(int j=0;j<n;j++){
					cout<<g[i][j]<<" ";
				}
				cout<<'\n';
			}
			
			
		}
		int dx[4] = {0,0,1,-1};
        int dy[4] = {1,-1,0,0};
        int res = 0;
        vector<vector<bool>>vis(n,vector<bool>(n,0));
		 for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(!vis[i][j] && g[i][j]){
					queue<pii>q;
					q.push({i,j});
					while(!q.empty()){
						int x = q.front().fi;
						int y = q.front().se;
						vis[x][y] = 1;
						q.pop();
						//cout<<x<<" "<<y<<'\n';
						for(int k=0;k<4;k++){
							int xn = x+dx[k];
							int yn = y+dy[k];
							if(xn>=0 && yn>=0 && xn<n && yn<n && g[xn][yn] && !vis[xn][yn]){
								q.push({xn,yn});
								vis[xn][yn] = 1;
							}
						}
						
					}
					res++;
				}
			}
		}
		for(int i=0;i<30;i++)if(res&(1<<i))ans[i] = '1';
	}
	return ans;
}

Subtask #1
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	2164 KB	Output is correct
2	Correct	8 ms	2292 KB	Output is correct
3	Correct	8 ms	2384 KB	Output is correct
4	Correct	8 ms	1980 KB	Output is correct
5	Correct	8 ms	2296 KB	Output is correct
6	Correct	8 ms	2096 KB	Output is correct

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	2164 KB	Output is correct
2	Correct	8 ms	2292 KB	Output is correct
3	Correct	8 ms	2384 KB	Output is correct
4	Correct	8 ms	1980 KB	Output is correct
5	Correct	8 ms	2296 KB	Output is correct
6	Correct	8 ms	2096 KB	Output is correct
7	Correct	11 ms	2192 KB	Output is correct
8	Correct	16 ms	2056 KB	Output is correct
9	Correct	16 ms	2256 KB	Output is correct
10	Correct	16 ms	2244 KB	Output is correct
11	Correct	16 ms	2124 KB	Output is correct
12	Correct	17 ms	2188 KB	Output is correct
13	Correct	16 ms	2232 KB	Output is correct

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	2164 KB	Output is correct
2	Correct	8 ms	2292 KB	Output is correct
3	Correct	8 ms	2384 KB	Output is correct
4	Correct	8 ms	1980 KB	Output is correct
5	Correct	8 ms	2296 KB	Output is correct
6	Correct	8 ms	2096 KB	Output is correct
7	Correct	11 ms	2192 KB	Output is correct
8	Correct	16 ms	2056 KB	Output is correct
9	Correct	16 ms	2256 KB	Output is correct
10	Correct	16 ms	2244 KB	Output is correct
11	Correct	16 ms	2124 KB	Output is correct
12	Correct	17 ms	2188 KB	Output is correct
13	Correct	16 ms	2232 KB	Output is correct
14	Correct	32 ms	2544 KB	Output is correct
15	Correct	46 ms	2392 KB	Output is correct
16	Correct	44 ms	2452 KB	Output is correct
17	Correct	47 ms	2500 KB	Output is correct
18	Correct	45 ms	2484 KB	Output is correct
19	Correct	47 ms	2536 KB	Output is correct
20	Correct	46 ms	2516 KB	Output is correct

Subtask #4
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	2164 KB	Output is correct
2	Correct	8 ms	2292 KB	Output is correct
3	Correct	8 ms	2384 KB	Output is correct
4	Correct	8 ms	1980 KB	Output is correct
5	Correct	8 ms	2296 KB	Output is correct
6	Correct	8 ms	2096 KB	Output is correct
7	Correct	11 ms	2192 KB	Output is correct
8	Correct	16 ms	2056 KB	Output is correct
9	Correct	16 ms	2256 KB	Output is correct
10	Correct	16 ms	2244 KB	Output is correct
11	Correct	16 ms	2124 KB	Output is correct
12	Correct	17 ms	2188 KB	Output is correct
13	Correct	16 ms	2232 KB	Output is correct
14	Correct	32 ms	2544 KB	Output is correct
15	Correct	46 ms	2392 KB	Output is correct
16	Correct	44 ms	2452 KB	Output is correct
17	Correct	47 ms	2500 KB	Output is correct
18	Correct	45 ms	2484 KB	Output is correct
19	Correct	47 ms	2536 KB	Output is correct
20	Correct	46 ms	2516 KB	Output is correct
21	Correct	73 ms	2588 KB	Output is correct
22	Correct	104 ms	2716 KB	Output is correct
23	Correct	97 ms	2736 KB	Output is correct
24	Correct	99 ms	2724 KB	Output is correct
25	Correct	105 ms	2832 KB	Output is correct
26	Correct	103 ms	2712 KB	Output is correct
27	Correct	110 ms	2704 KB	Output is correct
28	Correct	105 ms	2772 KB	Output is correct

Subtask #5
0.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	2164 KB	Output is correct
2	Correct	8 ms	2292 KB	Output is correct
3	Correct	8 ms	2384 KB	Output is correct
4	Correct	8 ms	1980 KB	Output is correct
5	Correct	8 ms	2296 KB	Output is correct
6	Correct	8 ms	2096 KB	Output is correct
7	Correct	11 ms	2192 KB	Output is correct
8	Correct	16 ms	2056 KB	Output is correct
9	Correct	16 ms	2256 KB	Output is correct
10	Correct	16 ms	2244 KB	Output is correct
11	Correct	16 ms	2124 KB	Output is correct
12	Correct	17 ms	2188 KB	Output is correct
13	Correct	16 ms	2232 KB	Output is correct
14	Correct	32 ms	2544 KB	Output is correct
15	Correct	46 ms	2392 KB	Output is correct
16	Correct	44 ms	2452 KB	Output is correct
17	Correct	47 ms	2500 KB	Output is correct
18	Correct	45 ms	2484 KB	Output is correct
19	Correct	47 ms	2536 KB	Output is correct
20	Correct	46 ms	2516 KB	Output is correct
21	Correct	73 ms	2588 KB	Output is correct
22	Correct	104 ms	2716 KB	Output is correct
23	Correct	97 ms	2736 KB	Output is correct
24	Correct	99 ms	2724 KB	Output is correct
25	Correct	105 ms	2832 KB	Output is correct
26	Correct	103 ms	2712 KB	Output is correct
27	Correct	110 ms	2704 KB	Output is correct
28	Correct	105 ms	2772 KB	Output is correct
29	Incorrect	20 ms	464 KB	Incorrect
30	Halted	0 ms	0 KB	-

Subtask #6
0.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	2164 KB	Output is correct
2	Correct	8 ms	2292 KB	Output is correct
3	Correct	8 ms	2384 KB	Output is correct
4	Correct	8 ms	1980 KB	Output is correct
5	Correct	8 ms	2296 KB	Output is correct
6	Correct	8 ms	2096 KB	Output is correct
7	Correct	11 ms	2192 KB	Output is correct
8	Correct	16 ms	2056 KB	Output is correct
9	Correct	16 ms	2256 KB	Output is correct
10	Correct	16 ms	2244 KB	Output is correct
11	Correct	16 ms	2124 KB	Output is correct
12	Correct	17 ms	2188 KB	Output is correct
13	Correct	16 ms	2232 KB	Output is correct
14	Correct	32 ms	2544 KB	Output is correct
15	Correct	46 ms	2392 KB	Output is correct
16	Correct	44 ms	2452 KB	Output is correct
17	Correct	47 ms	2500 KB	Output is correct
18	Correct	45 ms	2484 KB	Output is correct
19	Correct	47 ms	2536 KB	Output is correct
20	Correct	46 ms	2516 KB	Output is correct
21	Correct	73 ms	2588 KB	Output is correct
22	Correct	104 ms	2716 KB	Output is correct
23	Correct	97 ms	2736 KB	Output is correct
24	Correct	99 ms	2724 KB	Output is correct
25	Correct	105 ms	2832 KB	Output is correct
26	Correct	103 ms	2712 KB	Output is correct
27	Correct	110 ms	2704 KB	Output is correct
28	Correct	105 ms	2772 KB	Output is correct
29	Incorrect	20 ms	464 KB	Incorrect
30	Halted	0 ms	0 KB	-

Subtask #7
0.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	2164 KB	Output is correct
2	Correct	8 ms	2292 KB	Output is correct
3	Correct	8 ms	2384 KB	Output is correct
4	Correct	8 ms	1980 KB	Output is correct
5	Correct	8 ms	2296 KB	Output is correct
6	Correct	8 ms	2096 KB	Output is correct
7	Correct	11 ms	2192 KB	Output is correct
8	Correct	16 ms	2056 KB	Output is correct
9	Correct	16 ms	2256 KB	Output is correct
10	Correct	16 ms	2244 KB	Output is correct
11	Correct	16 ms	2124 KB	Output is correct
12	Correct	17 ms	2188 KB	Output is correct
13	Correct	16 ms	2232 KB	Output is correct
14	Correct	32 ms	2544 KB	Output is correct
15	Correct	46 ms	2392 KB	Output is correct
16	Correct	44 ms	2452 KB	Output is correct
17	Correct	47 ms	2500 KB	Output is correct
18	Correct	45 ms	2484 KB	Output is correct
19	Correct	47 ms	2536 KB	Output is correct
20	Correct	46 ms	2516 KB	Output is correct
21	Correct	73 ms	2588 KB	Output is correct
22	Correct	104 ms	2716 KB	Output is correct
23	Correct	97 ms	2736 KB	Output is correct
24	Correct	99 ms	2724 KB	Output is correct
25	Correct	105 ms	2832 KB	Output is correct
26	Correct	103 ms	2712 KB	Output is correct
27	Correct	110 ms	2704 KB	Output is correct
28	Correct	105 ms	2772 KB	Output is correct
29	Incorrect	20 ms	464 KB	Incorrect
30	Halted	0 ms	0 KB	-

Subtask #8
0.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	2164 KB	Output is correct
2	Correct	8 ms	2292 KB	Output is correct
3	Correct	8 ms	2384 KB	Output is correct
4	Correct	8 ms	1980 KB	Output is correct
5	Correct	8 ms	2296 KB	Output is correct
6	Correct	8 ms	2096 KB	Output is correct
7	Correct	11 ms	2192 KB	Output is correct
8	Correct	16 ms	2056 KB	Output is correct
9	Correct	16 ms	2256 KB	Output is correct
10	Correct	16 ms	2244 KB	Output is correct
11	Correct	16 ms	2124 KB	Output is correct
12	Correct	17 ms	2188 KB	Output is correct
13	Correct	16 ms	2232 KB	Output is correct
14	Correct	32 ms	2544 KB	Output is correct
15	Correct	46 ms	2392 KB	Output is correct
16	Correct	44 ms	2452 KB	Output is correct
17	Correct	47 ms	2500 KB	Output is correct
18	Correct	45 ms	2484 KB	Output is correct
19	Correct	47 ms	2536 KB	Output is correct
20	Correct	46 ms	2516 KB	Output is correct
21	Correct	73 ms	2588 KB	Output is correct
22	Correct	104 ms	2716 KB	Output is correct
23	Correct	97 ms	2736 KB	Output is correct
24	Correct	99 ms	2724 KB	Output is correct
25	Correct	105 ms	2832 KB	Output is correct
26	Correct	103 ms	2712 KB	Output is correct
27	Correct	110 ms	2704 KB	Output is correct
28	Correct	105 ms	2772 KB	Output is correct
29	Incorrect	20 ms	464 KB	Incorrect
30	Halted	0 ms	0 KB	-

Subtask #9
0.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	2164 KB	Output is correct
2	Correct	8 ms	2292 KB	Output is correct
3	Correct	8 ms	2384 KB	Output is correct
4	Correct	8 ms	1980 KB	Output is correct
5	Correct	8 ms	2296 KB	Output is correct
6	Correct	8 ms	2096 KB	Output is correct
7	Correct	11 ms	2192 KB	Output is correct
8	Correct	16 ms	2056 KB	Output is correct
9	Correct	16 ms	2256 KB	Output is correct
10	Correct	16 ms	2244 KB	Output is correct
11	Correct	16 ms	2124 KB	Output is correct
12	Correct	17 ms	2188 KB	Output is correct
13	Correct	16 ms	2232 KB	Output is correct
14	Correct	32 ms	2544 KB	Output is correct
15	Correct	46 ms	2392 KB	Output is correct
16	Correct	44 ms	2452 KB	Output is correct
17	Correct	47 ms	2500 KB	Output is correct
18	Correct	45 ms	2484 KB	Output is correct
19	Correct	47 ms	2536 KB	Output is correct
20	Correct	46 ms	2516 KB	Output is correct
21	Correct	73 ms	2588 KB	Output is correct
22	Correct	104 ms	2716 KB	Output is correct
23	Correct	97 ms	2736 KB	Output is correct
24	Correct	99 ms	2724 KB	Output is correct
25	Correct	105 ms	2832 KB	Output is correct
26	Correct	103 ms	2712 KB	Output is correct
27	Correct	110 ms	2704 KB	Output is correct
28	Correct	105 ms	2772 KB	Output is correct
29	Incorrect	20 ms	464 KB	Incorrect
30	Halted	0 ms	0 KB	-

Subtask #10
0.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	2164 KB	Output is correct
2	Correct	8 ms	2292 KB	Output is correct
3	Correct	8 ms	2384 KB	Output is correct
4	Correct	8 ms	1980 KB	Output is correct
5	Correct	8 ms	2296 KB	Output is correct
6	Correct	8 ms	2096 KB	Output is correct
7	Correct	11 ms	2192 KB	Output is correct
8	Correct	16 ms	2056 KB	Output is correct
9	Correct	16 ms	2256 KB	Output is correct
10	Correct	16 ms	2244 KB	Output is correct
11	Correct	16 ms	2124 KB	Output is correct
12	Correct	17 ms	2188 KB	Output is correct
13	Correct	16 ms	2232 KB	Output is correct
14	Correct	32 ms	2544 KB	Output is correct
15	Correct	46 ms	2392 KB	Output is correct
16	Correct	44 ms	2452 KB	Output is correct
17	Correct	47 ms	2500 KB	Output is correct
18	Correct	45 ms	2484 KB	Output is correct
19	Correct	47 ms	2536 KB	Output is correct
20	Correct	46 ms	2516 KB	Output is correct
21	Correct	73 ms	2588 KB	Output is correct
22	Correct	104 ms	2716 KB	Output is correct
23	Correct	97 ms	2736 KB	Output is correct
24	Correct	99 ms	2724 KB	Output is correct
25	Correct	105 ms	2832 KB	Output is correct
26	Correct	103 ms	2712 KB	Output is correct
27	Correct	110 ms	2704 KB	Output is correct
28	Correct	105 ms	2772 KB	Output is correct
29	Incorrect	20 ms	464 KB	Incorrect
30	Halted	0 ms	0 KB	-

Submission #593326

Compilation message