| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 731590 | ogibogi2004 | Game (APIO22_game) | 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>
using namespace std;
vector<vector<bool> > read_string(string s,int k)
{
//it should have k+2 * k+2
//i,j in (k+2)*i+j
vector<vector<bool> >ret;
for(int i=0;i<k+1;i++)
{
ret.push_back({});
for(int j=0;j<k+1;j++)
{
ret[i].push_back(s[(k+1)*i+j]);
}
}
//cout<<"?\n";
for(int i=0;i<(k+1)*(k+1);i++)
{
int x=i/(k+1);
int y=i%(k+1);
//cout<<x<<" "<<y<<endl;
ret[x][y]=s[i]-'0';
}
return ret;
}
string encode(vector<vector<bool> >v)
{
string ret="";
int t=v.size()/2+1;
for(int i=0;i<t*t;i++)ret+="0";
for(int i=0;i<v.size();i+=2)
{
for(int j=0;j<v.size();j+=2)
{
ret[(i/2)*t+j/2]=v[i][j]+'0';
}
}
while(ret.size()<100)ret+="0";
return ret;
}
bool vis[64][64];
vector<vector<bool> >matrix;
void dfs(int x,int y)
{
vis[x][y]=1;
if(x>0&&vis[x-1][y]==0&&matrix[x-1][y]==1)dfs(x-1,y);
if(y>0&&vis[x][y-1]==0&&matrix[x][y-1]==1)dfs(x,y-1);
if(x+1<matrix.size()&&vis[x+1][y]==0&&matrix[x+1][y]==1)dfs(x+1,y);
if(y+1<matrix.size()&&vis[x][y+1]==0&&matrix[x][y+1]==1)dfs(x,y+1);
}
string get_num_islands(vector<vector<bool> >v)
{
/*cout<<"--------------\n";
for(auto xd:v)
{
for(auto dx:xd)cout<<dx<<" ";
cout<<endl;
}
cout<<"--------------\n";*/
int cnt=0;
memset(vis,0,sizeof(vis));
matrix=v;
for(int i=0;i<v.size();i++)
{
for(int j=0;j<v[i].size();j++)
{
if(vis[i][j]==0&&v[i][j]==1)
{
dfs(i,j);
cnt++;
}
}
}
string bin="";
//cout<<cnt<<endl;
while(cnt)
{
bin+=char(cnt%2+'0');
cnt/=2;
}
//reverse(bin.begin(),bin.end());
while(bin.size()<100)bin+="0";
return bin;
}
void print(vector<vector<bool> >v)
{
cout<<"--------------\n";
for(auto xd:v)
{
for(auto dx:xd)cout<<dx<<" ";
cout<<endl;
}
cout<<"--------------\n";
}
string process(vector <vector<string>> a, int i, int j, int k, int n)
{
//cout<<i<<" "<<j<<" "<<k<<endl;
if(k<n-1)
{
vector<vector<bool> >actual_table;
for(int it1=0;it1<2*k+3;it1++)
{
actual_table.push_back({});
for(int it2=0;it2<2*k+3;it2++)
{
actual_table[it1].push_back(0);
}
}
for(int i1=0;i1<3;i1++)
{
for(int i2=0;i2<3;i2++)
{
vector<vector<bool> >subtable = read_string(a[i1][i2],k);
for(int dx=0;dx<subtable.size()&&i1+dx*2<actual_table.size();dx++)
{
for(int dy=0;dy<subtable[dx].size()&&i2+dy*2<actual_table.size();dy++)
{
actual_table[i1+dx*2][i2+dy*2]=max(actual_table[i1+dx*2][i2+dy*2],subtable[dx][dy]);
}
}
}
}
//cout<<"returned "<<i<<" "<<j<<" "<<k<<" "<<encode(actual_table)<<endl;
//print(actual_table);
return encode(actual_table);
}
else
{
vector<vector<bool> >actual_table;
for(int it1=0;it1<2*k+3;it1++)
{
actual_table.push_back({});
for(int it2=0;it2<2*k+3;it2++)
{
actual_table[it1].push_back(0);
}
}
//cout<<"*1\n";
for(int i1=0;i1<3;i1++)
{
for(int i2=0;i2<3;i2++)
{
//cout<<i1<<" "<<i2<<endl;
vector<vector<bool> >subtable = read_string(a[i1][i2],k);
//print(subtable);
//cout<<"alo\n";
for(int dx=0;dx<subtable.size()&&i1+dx*2<actual_table.size();dx++)
{
for(int dy=0;dy<subtable[dx].size()&&i2+dy*2<actual_table.size();dy++)
{
//cout<<i1+dx*2<<" "<<i2+dy*2<<endl;
actual_table[i1+dx*2][i2+dy*2]=max(actual_table[i1+dx*2][i2+dy*2],subtable[dx][dy]);
}
}
}
}
//cout<<"*2\n";
return get_num_islands(actual_table);
}
}