| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 725271 |
2023-04-17T06:16:45 Z |
Nahian9696 |
Mars (APIO22_mars) |
C++17 |
|
1 ms |
200 KB |
#include "mars.h"
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define f0(i, n) for(int i = 0; i < (n); i++)
#define f1(i, n) for(int i = 1; i <= (n); i++)
#define ff first
#define ss second
std::string process(std::vector <std::vector<std::string>> a, int i, int j, int k, int n)
{
string res;
f0(i, 100) res += '0';
int ii = i/2, jj = j/2;
if(k == 0) {
if(n == 1) {
bool grph[2*n+1][2*n+1] = {0};
bool vis[2*n+1][2*n+1] = {0};
int cnt = 0;
f0(i, 2*n+1) {
f0(j, 2*n+1) {
if(a[i][j][0] == '1') grph[i][j] = 1;
}
}
queue<pair<int, int>> q;
f0(i, 2*n+1) {
f0(j, 2*n+1) {
// cout << grph[i][j] << " ";
if(!grph[i][j]) continue;
if(vis[i][j]) continue;
vis[i][j] = 1;
cnt++;
q.push({i, j});
while(!q.empty()) {
auto cur = q.front();
int x = cur.ff, y = cur.ss;
// if(vis[x][y]) continue;
q.pop();
if(x+1 < 2*n+1) {
if(grph[x+1][y] == 1) {
if(!vis[x+1][y]) {
vis[x+1][y] = 1;
q.push({x+1, y});
}
}
}
if(y+1 < 2*n+1) {
if(grph[x][y+1] == 1) {
if(!vis[x][y+1]) {
vis[x][y+1] = 1;
q.push({x, y+1});
}
}
}
if(x > 0) {
if(grph[x-1][y] == 1) {
if(!vis[x-1][y]) {
vis[x-1][y] = 1;
q.push({x-1, y});
}
}
}
if(y > 0) {
if(grph[x][y-1] == 1) {
if(!vis[x][y-1]) {
vis[x][y-1] = 1;
q.push({x, y-1});
}
}
}
}
}
// cout << endl;
}
// cout << cnt << "\n";
res = "";
while(cnt > 0) {
res += '0' + (cnt%2);
cnt /= 2;
}
// res = string(res.rbegin(), res.rend());
int nn = res.size();
// string res0;
f0(i, 100-nn) res += '0';
// cout << res0+res << endl;
return res;
}
if( (i % 2 == 0) && (j % 2 == 0) ) {
if(a[0][0][0] == '1') {
a[0][0] = res;
a[0][0][ (n+1)*(jj) + (ii) ] = '1';
} else {
a[0][0] = res;
}
if(a[0][2][0] == '1') {
a[0][2] = res;
a[0][2][ (n+1)*(jj+1) + (ii) ] = '1';
} else {
a[0][2] = res;
}
if(a[2][0][0] == '1') {
a[2][0] = res;
a[2][0][ (n+1)*(jj) + (ii+1) ] = '1';
} else {
a[2][0] = res;
}
if(a[2][2][0] == '1') {
a[2][2] = res;
a[2][2][ (n+1)*(jj+1) + (ii+1) ] = '1';
} else {
a[2][2] = res;
}
} else if( (i % 2 == 1) && (j % 2 == 0) ) {
if(a[0][0][0] == '1') {
a[0][0] = res;
a[0][0][ (n)*(jj) + (ii) ] = '1';
} else {
a[0][0] = res;
}
if(a[0][2][0] == '1') {
a[0][2] = res;
a[0][2][ (n)*(jj+1) + (ii) ] = '1';
} else {
a[0][2] = res;
}
if(a[2][0][0] == '1') {
a[2][0] = res;
a[2][0][ (n)*(jj) + (ii+1) ] = '1';
} else {
a[2][0] = res;
}
if(a[2][2][0] == '1') {
a[2][2] = res;
a[2][2][ (n)*(jj+1) + (ii+1) ] = '1';
} else {
a[2][2] = res;
}
} else if( (i % 2 == 0) && (j % 2 == 1) ) {
if(a[0][0][0] == '1') {
a[0][0] = res;
a[0][0][ (n+1)*(jj) + (ii) ] = '1';
} else {
a[0][0] = res;
}
if(a[0][2][0] == '1') {
a[0][2] = res;
a[0][2][ (n+1)*(jj+1) + (ii) ] = '1';
} else {
a[0][2] = res;
}
if(a[2][0][0] == '1') {
a[2][0] = res;
a[2][0][ (n+1)*(jj) + (ii+1) ] = '1';
} else {
a[2][0] = res;
}
if(a[2][2][0] == '1') {
a[2][2] = res;
a[2][2][ (n+1)*(jj+1) + (ii+1) ] = '1';
} else {
a[2][2] = res;
}
} else if( (i % 2 == 1) && (j % 2 == 1) ) {
if(a[0][0][0] == '1') {
a[0][0] = res;
a[0][0][ (n)*(jj) + (ii) ] = '1';
} else {
a[0][0] = res;
}
if(a[0][2][0] == '1') {
a[0][2] = res;
a[0][2][ (n)*(jj+1) + (ii) ] = '1';
} else {
a[0][2] = res;
}
if(a[2][0][0] == '1') {
a[2][0] = res;
a[2][0][ (n)*(jj) + (ii+1) ] = '1';
} else {
a[2][0] = res;
}
if(a[2][2][0] == '1') {
a[2][2] = res;
a[2][2][ (n)*(jj+1) + (ii+1) ] = '1';
} else {
a[2][2] = res;
}
}
}
f0(i, 100) {
if (
(a[0][0][i] == '1') ||
(a[2][0][i] == '1') ||
(a[0][2][i] == '1') ||
(a[2][2][i] == '1')
) {
res[i] = '1';
}
}
if(k == (n-1)) {
bool grph[2*n+1][2*n+1] = {0};
bool vis[2*n+1][2*n+1] = {0};
int cnt = 0;
f0(i, (n+1)*(n+1)) {
int y = i/(n+1), x = i % (n+1);
if(a[0][0][i] == '1') {
grph[2*x][2*y] = 1;
}
if(a[0][2][i] == '1') {
grph[2*x][2*y] = 1;
}
if(a[2][0][i] == '1') {
grph[2*x][2*y] = 1;
}
if(a[2][2][i] == '1') {
grph[2*x][2*y] = 1;
}
}
f0(i, n*(n+1)) {
int y = i/(n+1), x = i % (n+1);
if(a[0][1][i] == '1') {
grph[2*x][2*y+1] = 1;
}
if(a[2][1][i] == '1') {
grph[2*x][2*y+1] = 1;
}
}
f0(i, (n+1)*n) {
int y = i/n, x = i % n;
if(a[1][0][i] == '1') {
grph[2*x+1][2*y] = 1;
}
if(a[1][2][i] == '1') {
grph[2*x+1][2*y] = 1;
}
}
f0(i, n*n) {
int y = i/n, x = i % n;
if(a[1][1][i] == '1') {
grph[2*x+1][2*y+1] = 1;
}
}
queue<pair<int, int>> q;
f0(i, 2*n+1) {
f0(j, 2*n+1) {
if(!grph[i][j]) continue;
// cout << grph[i][j] << " ";
if(vis[i][j]) continue;
vis[i][j] = 1;
cnt++;
q.push({i, j});
while(!q.empty()) {
auto cur = q.front();
int x = cur.ff, y = cur.ss;
// if(vis[x][y]) continue;
q.pop();
if(x+1 < 2*n+1) {
if(grph[x+1][y] == 1) {
if(!vis[x+1][y]) {
vis[x+1][y] = 1;
q.push({x+1, y});
}
}
}
if(y+1 < 2*n+1) {
if(grph[x][y+1] == 1) {
if(!vis[x][y+1]) {
vis[x][y+1] = 1;
q.push({x, y+1});
}
}
}
if(x > 0) {
if(grph[x-1][y] == 1) {
if(!vis[x-1][y]) {
vis[x-1][y] = 1;
q.push({x-1, y});
}
}
}
if(y > 0) {
if(grph[x][y-1] == 1) {
if(!vis[x][y-1]) {
vis[x][y-1] = 1;
q.push({x, y-1});
}
}
}
}
}
// cout << endl;
}
// cout << cnt << "\n";
res = "";
while(cnt > 0) {
res += '0' + (cnt%2);
cnt /= 2;
}
// res = string(res.rbegin(), res.rend());
int nn = res.size();
// string res0;
f0(i, 100-nn) res += '0';
// cout << res0+res << endl;
return res;
}
return res;
return std::string(100 ,'0');
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
