oj.uz

Submission #1088739

# Submission time Handle Problem Language Result Execution time Memory
1088739 2024-09-14T23:09:37 Z Math4Life2020 Mars (APIO22_mars) C++17
14 / 100
 15 ms 3292 KB 
#include <bits/stdc++.h>
#include "mars.h"
using namespace std;
using ll = long long; using pii = pair<ll,ll>;

string process(vector<vector<char>> land, int N) {
	bool bl[N][N];
	bool found[N][N];
	for (ll i=0;i<N;i++) {
		for (ll j=0;j<N;j++) {
			//cout << "i="<<i<<", j="<<j<<", land="<<land[i][j]<<"\n";
			found[i][j]=0;
			if (land[i][j]=='x') {
				assert(1==2);
			} else if (land[i][j]=='0') {
				bl[i][j]=0;
			} else if (land[i][j]=='1') {
				bl[i][j]=1;
			}
		}
		//cout << "\n";
	}
	ll ans = 0;
	for (ll i=0;i<N;i++) {
		for (ll j=0;j<N;j++) {
			if (found[i][j] || !bl[i][j]) {
				continue;
			}
			ans++;
			stack<pii> s;
			s.push({i,j});
			while (!s.empty()) {
				pii pt = s.top(); s.pop();
				ll x = pt.first; ll y = pt.second;
				//cout << "x,y="<<x<<","<<y<<"\n";
				if (x<0 || x>=N) {
					continue;
				}
				if (y<0 || y>=N) {
					continue;
				}
				if (bl[x][y] && !found[x][y]) {
					//cout << "f1\n";
					found[x][y]=1;
					s.push({x+1,y});
					s.push({x-1,y});
					s.push({x,y-1});
					s.push({x,y+1});
				}
			}
		}
	}
	string outstr;
	for (ll i=0;i<100;i++) {
		outstr += "0";
	}
	for (ll i=0;i<20;i++) {
		if ((ans>>i)&1) {
			outstr[i]='1';
		}
	}
	return outstr;
}

string process(vector<vector<string>> a, int i, int j, int K, int N) {
	if (K==(N-1)) {
		vector<pii> nums[2*N+1][2*N+1];
		vector<vector<char>> land;
		for (ll is=0;is<(2*N+1);is++) {
			vector<char> vcharblank;
			for (ll js=0;js<(2*N+1);js++) {
				nums[is][js].push_back({is,js});
				vcharblank.push_back('x');
			}
			land.push_back(vcharblank);
		}
		for (ll ks=0;ks<K;ks++) {
			ll ms = 2*(N-ks-1);
			for (ll js=0;js<=ms;js++) {
				for (ll is=0;is<=ms;is++) {
					if (is==ms && js!=ms) {
						for (pii ps: nums[is+1][js]) {
							nums[is][js].push_back(ps);
						}
						for (pii ps: nums[is+2][js]) {
							nums[is][js].push_back(ps);
						}
					}
					if (is!=ms && js==ms) {
						for (pii ps: nums[is][js+1]) {
							nums[is][js].push_back(ps);
						}
						for (pii ps: nums[is][js+2]) {
							nums[is][js].push_back(ps);
						}
					}
					if (is==ms && js==ms) {
						for (ll I=0;I<3;I++) {
							for (ll J=0;J<3;J++) {
								if (I==0 && J==0) {
									continue;
								}
								for (pii ps: nums[is+I][js+J]) {
									nums[is][js].push_back(ps);
								}
							}
						}
					}
				}
			}
		}
		/*for (ll i1=0;i1<3;i1++) {
			for (ll j1=0;j1<3;j1++) {
				cout << "i,j="<<i1<<","<<j1<<"\n";
				for (pii px: nums[i1][j1]) {
					cout << "px="<<px.first<<","<<px.second<<"\n";
				}
			}
		}*/
		for (ll I=0;I<3;I++) {
			for (ll J=0;J<3;J++) {
				for (ll t=0;t<nums[I][J].size();t++) {
					ll x0 = nums[I][J][t].first; ll y0 = nums[I][J][t].second;
					//cout << "x0,y0="<<x0<<","<<y0<<"\n";
					land[x0][y0]=a[I][J][t];
					//cout << "land[x="<<x0<<"][y0="<<y0<<"]="<<land[x0][y0]<<"\n";
				}
			}
		}
		return process(land,2*N+1);
		//return "";
	} else {
		string out = a[0][0];
		ll m = 2*(N-K-1);
		if (i==m && j!=m) {
			out[1]=a[1][0][0]; //first character
			for (ll t=0;t<98;t++) {
				out[t+2]=a[2][0][t];
			}
			return out;
		} else if (i!=m && j==m) {
			out[1]=a[0][1][0];
			for (ll t=0;t<98;t++) {
				out[t+2]=a[0][2][t];
			}
			return out;
		} else if (i==m && j==m) {
			ll d = 2*N+1-(i+2);
			ll T = 1;
			out[1]=a[0][1][0]; T++;
			for (ll t=0;t<d;t++) {
				out[T++]=a[0][2][t];
			}
			out[T++]=a[1][0][0];
			out[T++]=a[1][1][0];
			for (ll t=0;t<d;t++) {
				out[T++]=a[1][2][t];
			}
			for (ll t=0;t<d;t++) {
				out[T++]=a[2][0][t];
			}
			for (ll t=0;t<d;t++) {
				out[T++]=a[2][1][t];
			}
			for (ll t=0;t<(d*d);t++) {
				out[T++]=a[2][2][t];
			}
			return out;
		} else {
			return out;
		}
	}
}

vector<vector<string>> sbr(vector<vector<string>> inpts, ll x, ll y) {
	vector<vector<string>> out;
	for (ll i=0;i<3;i++) {
		vector<string> o1 = {"","",""};
		out.push_back(o1);
	}
	for (ll i=0;i<3;i++) {
		for (ll j=0;j<3;j++) {
			out[i][j]=inpts[x+i][y+j];
		}
	}
	return out;
}

Compilation message

mars.cpp: In function 'std::string process(std::vector<std::vector<std::__cxx11::basic_string<char> > >, int, int, int, int)':
mars.cpp:122:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |     for (ll t=0;t<nums[I][J].size();t++) {
      |                 ~^~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2768 KB Output is correct
2 Correct 7 ms 2852 KB Output is correct
3 Correct 7 ms 3144 KB Output is correct
4 Correct 6 ms 2840 KB Output is correct
5 Correct 6 ms 3184 KB Output is correct
6 Correct 8 ms 2776 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2768 KB Output is correct
2 Correct 7 ms 2852 KB Output is correct
3 Correct 7 ms 3144 KB Output is correct
4 Correct 6 ms 2840 KB Output is correct
5 Correct 6 ms 3184 KB Output is correct
6 Correct 8 ms 2776 KB Output is correct
7 Correct 8 ms 2964 KB Output is correct
8 Correct 8 ms 3292 KB Output is correct
9 Correct 9 ms 3240 KB Output is correct
10 Correct 9 ms 3156 KB Output is correct
11 Correct 13 ms 3120 KB Output is correct
12 Correct 9 ms 3000 KB Output is correct
13 Correct 15 ms 2832 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2768 KB Output is correct
2 Correct 7 ms 2852 KB Output is correct
3 Correct 7 ms 3144 KB Output is correct
4 Correct 6 ms 2840 KB Output is correct
5 Correct 6 ms 3184 KB Output is correct
6 Correct 8 ms 2776 KB Output is correct
7 Correct 8 ms 2964 KB Output is correct
8 Correct 8 ms 3292 KB Output is correct
9 Correct 9 ms 3240 KB Output is correct
10 Correct 9 ms 3156 KB Output is correct
11 Correct 13 ms 3120 KB Output is correct
12 Correct 9 ms 3000 KB Output is correct
13 Correct 15 ms 2832 KB Output is correct
14 Runtime error 2 ms 452 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2768 KB Output is correct
2 Correct 7 ms 2852 KB Output is correct
3 Correct 7 ms 3144 KB Output is correct
4 Correct 6 ms 2840 KB Output is correct
5 Correct 6 ms 3184 KB Output is correct
6 Correct 8 ms 2776 KB Output is correct
7 Correct 8 ms 2964 KB Output is correct
8 Correct 8 ms 3292 KB Output is correct
9 Correct 9 ms 3240 KB Output is correct
10 Correct 9 ms 3156 KB Output is correct
11 Correct 13 ms 3120 KB Output is correct
12 Correct 9 ms 3000 KB Output is correct
13 Correct 15 ms 2832 KB Output is correct
14 Runtime error 2 ms 452 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2768 KB Output is correct
2 Correct 7 ms 2852 KB Output is correct
3 Correct 7 ms 3144 KB Output is correct
4 Correct 6 ms 2840 KB Output is correct
5 Correct 6 ms 3184 KB Output is correct
6 Correct 8 ms 2776 KB Output is correct
7 Correct 8 ms 2964 KB Output is correct
8 Correct 8 ms 3292 KB Output is correct
9 Correct 9 ms 3240 KB Output is correct
10 Correct 9 ms 3156 KB Output is correct
11 Correct 13 ms 3120 KB Output is correct
12 Correct 9 ms 3000 KB Output is correct
13 Correct 15 ms 2832 KB Output is correct
14 Runtime error 2 ms 452 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #6
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2768 KB Output is correct
2 Correct 7 ms 2852 KB Output is correct
3 Correct 7 ms 3144 KB Output is correct
4 Correct 6 ms 2840 KB Output is correct
5 Correct 6 ms 3184 KB Output is correct
6 Correct 8 ms 2776 KB Output is correct
7 Correct 8 ms 2964 KB Output is correct
8 Correct 8 ms 3292 KB Output is correct
9 Correct 9 ms 3240 KB Output is correct
10 Correct 9 ms 3156 KB Output is correct
11 Correct 13 ms 3120 KB Output is correct
12 Correct 9 ms 3000 KB Output is correct
13 Correct 15 ms 2832 KB Output is correct
14 Runtime error 2 ms 452 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2768 KB Output is correct
2 Correct 7 ms 2852 KB Output is correct
3 Correct 7 ms 3144 KB Output is correct
4 Correct 6 ms 2840 KB Output is correct
5 Correct 6 ms 3184 KB Output is correct
6 Correct 8 ms 2776 KB Output is correct
7 Correct 8 ms 2964 KB Output is correct
8 Correct 8 ms 3292 KB Output is correct
9 Correct 9 ms 3240 KB Output is correct
10 Correct 9 ms 3156 KB Output is correct
11 Correct 13 ms 3120 KB Output is correct
12 Correct 9 ms 3000 KB Output is correct
13 Correct 15 ms 2832 KB Output is correct
14 Runtime error 2 ms 452 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #8
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2768 KB Output is correct
2 Correct 7 ms 2852 KB Output is correct
3 Correct 7 ms 3144 KB Output is correct
4 Correct 6 ms 2840 KB Output is correct
5 Correct 6 ms 3184 KB Output is correct
6 Correct 8 ms 2776 KB Output is correct
7 Correct 8 ms 2964 KB Output is correct
8 Correct 8 ms 3292 KB Output is correct
9 Correct 9 ms 3240 KB Output is correct
10 Correct 9 ms 3156 KB Output is correct
11 Correct 13 ms 3120 KB Output is correct
12 Correct 9 ms 3000 KB Output is correct
13 Correct 15 ms 2832 KB Output is correct
14 Runtime error 2 ms 452 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #9
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2768 KB Output is correct
2 Correct 7 ms 2852 KB Output is correct
3 Correct 7 ms 3144 KB Output is correct
4 Correct 6 ms 2840 KB Output is correct
5 Correct 6 ms 3184 KB Output is correct
6 Correct 8 ms 2776 KB Output is correct
7 Correct 8 ms 2964 KB Output is correct
8 Correct 8 ms 3292 KB Output is correct
9 Correct 9 ms 3240 KB Output is correct
10 Correct 9 ms 3156 KB Output is correct
11 Correct 13 ms 3120 KB Output is correct
12 Correct 9 ms 3000 KB Output is correct
13 Correct 15 ms 2832 KB Output is correct
14 Runtime error 2 ms 452 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #10
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2768 KB Output is correct
2 Correct 7 ms 2852 KB Output is correct
3 Correct 7 ms 3144 KB Output is correct
4 Correct 6 ms 2840 KB Output is correct
5 Correct 6 ms 3184 KB Output is correct
6 Correct 8 ms 2776 KB Output is correct
7 Correct 8 ms 2964 KB Output is correct
8 Correct 8 ms 3292 KB Output is correct
9 Correct 9 ms 3240 KB Output is correct
10 Correct 9 ms 3156 KB Output is correct
11 Correct 13 ms 3120 KB Output is correct
12 Correct 9 ms 3000 KB Output is correct
13 Correct 15 ms 2832 KB Output is correct
14 Runtime error 2 ms 452 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -