| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1225261 | KALARRY | 화성 (APIO22_mars) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <string>
#include <bitset>
using namespace std;
static void WA(string msg)
{
cout << "WA: " << msg << endl;
exit(0);
}
static long long to_longlong(string s)
{
long long ans=0;
for(int i=(int)s.size()-1;i>=0;i--)
ans=(ans*2)+s[i]-'0';
return ans;
}
//chockolateman
#include<bits/stdc++.h>
using namespace std;
int N,status[100][100][500];
pair<int,int> info[100][100][500]; //info[i][j][k] = shows that for (i,j) the kth bit has info for info[i][j][k]
pair<pair<int,int>,int> take_it_from[100][100][500];
int s_i[100][100];
bool found[100][100];
void calc_info()
{
for(int i = 0 ; i < N ; i++)
for(int j = 0 ; j < N ; j++)
{
s_i[i][j] = 1;
info[i][j][0] = {i,j};
}
for(int i = N-1 ; i >= 0 ; i--)
for(int j = N-1 ; j >= 0 ; j--)
{
for(int x = 0 ; x < N ; x++)
for(int y = 0 ; y < N ; y++)
found[x][y] = false;
found[i][j] = true;
take_it_from[i][j][0] = {{i,j},0};
int cur_pos = 1;
for(int x = i+2 ; x >= i ; x--)
for(int y = j+2 ; y >= j ; y--)
{
if(x==i && y==j)
continue;
s_i[i][j] += s_i[x][y];
for(int l = 0 ; l < s_i[x][y] ; l++)
{
if(found[info[x][y][l].first][info[x][y][l].second])
{
s_i[i][j]--;
continue;
}
info[i][j][cur_pos++] = info[x][y][l];
take_it_from[i][j][cur_pos - 1] = {{x,y},l};
found[info[x][y][l].first][info[x][y][l].second] = true;
}
}
}
}
int grid[100][100],di[4] = {1,-1,0,0},dj[4] = {0,0,1,-1};
bool visited[100][100];
void dfs(int i,int j)
{
if(i < 0 || i >= N || j < 0 || j >= N)
return;
if(visited[i][j])
return;
visited[i][j] = true;
for(int k = 0 ; k <= 3 ; k++)
{
int x = i + di[k];
int y = j + dj[k];
dfs(x,y);
}
}
long long solve()
{
memset(visited,false,sizeof(visited));
for(int i = 0 ; i < N ; i++)
for(int j = 0 ; j < N ; j++)
if(grid[i][j]==0)
visited[i][j] = true;
int ret = 0;
for(int i = 0 ; i < N ; i++)
for(int j = 0 ; j < N ; j++)
if(!visited[i][j])
{
ret++;
dfs(i,j);
}
return ret;
}
std::string process(std::vector <std::vector<std::string>> a, int i, int j, int k, int n)
{
N = 2*n + 1;
calc_info();
std::string ret(100 ,'0');
for(int l = 0 ; l < s_i[i][j] ; l++)
{
int x = take_it_from[i][j][l].first.first;
int y = take_it_from[i][j][l].first.second;
int r = take_it_from[i][j][l].second;
status[i][j][l] = a[x-i][y-j][r] - '0';
ret[l] = a[x-i][y-j][r];
}
if(k==n-1)
{
for(int l = 0 ; l < s_i[i][j] ; l++)
{
int x = info[i][j][l].first;
int y = info[i][j][l].second;
grid[x][y] = status[i][j][l];
}
int ans = solve();
int pos = 0;
for(int l = 0 ; l <= 99 ; l++)
{
ret[l] = ans%2 + '0';
ans /= 2;
}
}
return ret;
}
int main()
{
int t;
assert(scanf("%d",&t) == 1);
while(t--)
{
int n;
assert(scanf("%d",&n) == 1);
vector <vector<char>> s(2*n+1, vector<char>(2*n+1));
for(int i = 0; i < 2*n+1; i++)
for(int j = 0; j < 2*n+1; j++)
assert(scanf(" %c",&s[i][j]) == 1);
vector <vector<string>> h(2*n+1, vector<string>(2*n+1, string(100 ,'0')));
for(int i = 0; i < 2*n+1; i++)
for(int j = 0; j < 2*n+1; j++)
h[i][j][0] = s[i][j];
vector <vector<string>> subarr(3, vector<string>(3));
for(int k = 0; k < n; k++)
{
int m = 2*(n-k-1);
for(int i = 0; i <= m; i++)
{
for(int j = 0; j <= m; j++)
{
for(int y = 0; y < 3; y++)
{
for(int x = 0; x < 3; x++)
{
subarr[y][x] = h[i+y][j+x];
}
}
h[i][j] = process(subarr, i, j, k, n);
if(h[i][j].size() != 100) WA("Invalid return length");
for(int l = 0; l < 100; l++)
if(h[i][j][l] != '0' && h[i][j][l] != '1') WA("Invalid return");
}
}
}
printf("%lld\n",to_longlong(h[0][0]));
}
}