Submission #731591

#	Time	Username	Problem	Language	Result	Execution time	Memory
731591		ogibogi2004	Mars (APIO22_mars)	C++17	36 / 100	255 ms	3172 KiB

mars

#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);
    }
}

Compilation message (stderr)

mars.cpp: In function 'std::string encode(std::vector<std::vector<bool> >)':
mars.cpp:32:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int i=0;i<v.size();i+=2)
      |                 ~^~~~~~~~~
mars.cpp:34:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         for(int j=0;j<v.size();j+=2)
      |                     ~^~~~~~~~~
mars.cpp: In function 'void dfs(int, int)':
mars.cpp:49:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     if(x+1<matrix.size()&&vis[x+1][y]==0&&matrix[x+1][y]==1)dfs(x+1,y);
      |        ~~~^~~~~~~~~~~~~~
mars.cpp:50:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     if(y+1<matrix.size()&&vis[x][y+1]==0&&matrix[x][y+1]==1)dfs(x,y+1);
      |        ~~~^~~~~~~~~~~~~~
mars.cpp: In function 'std::string get_num_islands(std::vector<std::vector<bool> >)':
mars.cpp:64:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for(int i=0;i<v.size();i++)
      |                 ~^~~~~~~~~
mars.cpp:66:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for(int j=0;j<v[i].size();j++)
      |                     ~^~~~~~~~~~~~
mars.cpp: In function 'std::string process(std::vector<std::vector<std::__cxx11::basic_string<char> > >, int, int, int, int)':
mars.cpp:115:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |                 for(int dx=0;dx<subtable.size()&&i1+dx*2<actual_table.size();dx++)
      |                              ~~^~~~~~~~~~~~~~~~
mars.cpp:115:57: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |                 for(int dx=0;dx<subtable.size()&&i1+dx*2<actual_table.size();dx++)
      |                                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~
mars.cpp:117:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |                     for(int dy=0;dy<subtable[dx].size()&&i2+dy*2<actual_table.size();dy++)
      |                                  ~~^~~~~~~~~~~~~~~~~~~~
mars.cpp:117:65: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |                     for(int dy=0;dy<subtable[dx].size()&&i2+dy*2<actual_table.size();dy++)
      |                                                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~
mars.cpp:148:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |                 for(int dx=0;dx<subtable.size()&&i1+dx*2<actual_table.size();dx++)
      |                              ~~^~~~~~~~~~~~~~~~
mars.cpp:148:57: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |                 for(int dx=0;dx<subtable.size()&&i1+dx*2<actual_table.size();dx++)
      |                                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~
mars.cpp:150:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |                     for(int dy=0;dy<subtable[dx].size()&&i2+dy*2<actual_table.size();dy++)
      |                                  ~~^~~~~~~~~~~~~~~~~~~~
mars.cpp:150:65: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |                     for(int dy=0;dy<subtable[dx].size()&&i2+dy*2<actual_table.size();dy++)
      |                                                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 7 / 7
• Subtask 4: 8 / 8
• Subtask 5: 7 / 7
• Subtask 6: 0 / 8
• Subtask 7: 0 / 10
• Subtask 8: 0 / 24
• Subtask 9: 0 / 11
• Subtask 10: 0 / 11