| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 727727 | anusha777 | Mars (APIO22_mars) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "mars.h"
#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(0); cin.tie(NULL);cout.tie(NULL)
#define sz(x) (int)((x).size())
#define pb push_back
#define vi vector<int>
#define vb vector<bool>
#define vvb vector<vb>
#define pi pair<int,int>
#define vpi vector<pi>
#define vvi vector<vi>
#define vvs vector <vector<string>>
#define vc vector<char>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pbb() pop_back()
#define f first
#define s second
#define ll long long
#define int long long
#define ull unsigned long long
#define line cout<<"_____________________________"<<endl;
#define forr(i, a, b) for(int i=a; i<b; i++)
const int N=1e5+1, mod=998244353, inf=1e18+1;
using namespace std;
vi dx={0, 1, 0, -1}, dy={1, 0, -1, 0};
string phase0(vvs& a, int& x, int& y)
{
string s;
forr(i, 0, 3) forr(j, 0, 3) s.pb(a[i][j][0]);
forr(i , 9, 100) s.pb('0');
return s;
}
vvb vis(5, vb(5));
vvi g(5, vi(5));
void bfs(int x, int y)
{
queue<pi> q;
q.push({x, y});
while(!q.empty())
{
pi t= q.front();
q.pop();
if(vis[t.f][t.s]) continue;
vis[t.f][t.s]=1;
forr(i, 0, 4)
{
int xt= t.f+dx[i], yt= t.s+ dy[i];
if(xt>=0 and xt<5 and yt>=0 and yt<5) if(!vis[xt][yt] and g[xt][yt]==1)
q.push({xt, yt});
}
}
}
string process(vvs a, int i, int j, int k, int n)
{
if(k==0) return phase0(a, i, j);
forr(i, 0, 3) forr(j, 0, 3) forr(k, 0, 9)
{
int ii= i + k%3, jj= j+ k/3;
g[ii][jj]= a[i][j][k]-'0';
}
int total=0;
forr(i, 0, 5) forr(j, 0, 5) if(!vis[i][j] and g[i][j]==1)
{
bfs(i, j);
total++;
}
string ans;
for(int i=0 , mask=1; i<100; i++, mask*=2)
{
if((total&mask)==mask) ans.pb('1');
else ans.pb('0');
}
return ans;
}
#include "mars.h"
#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;
}
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]));
}
}