Submission #910894

#	Time	Username	Problem	Language	Result	Execution time	Memory
910894		ibm2006	Land of the Rainbow Gold (APIO17_rainbow)	C++17	0 / 100	509 ms	89276 KiB

rainbow

#include "rainbow.h"
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
ll n,m,i,j,l,r,x,y,z,w,s,t,cc[1100000],dx,dy,ddx[11000],ddy[11000];
char c;
pair<ll,ll> p[1100000],q;
map<pair<ll,ll>,ll> mp,mpp;
vector<ll> v[1100000];
vector<pair<ll,ll>> u;
void init(int R, int C, int sr, int sc, int M, char *S) {
    ddx[0]=1;  ddy[0]=0;
    ddx[1]=1;  ddy[1]=1;
    ddx[2]=1;  ddy[2]=-1;
    ddx[3]=0;  ddy[3]=1;
    ddx[4]=0;  ddy[4]=-1;
    ddx[5]=-1;  ddy[5]=1;
    ddx[6]=-1;  ddy[6]=0;
    ddx[7]=-1;  ddy[7]=-1;
    n=R;
    m=C;
    x=sr;
    y=sc;
    p[1]={x,y};
    mp[p[1]]=2;
    for(i=2;i<=M+1;i++)
    {
        c=S[i-2];
        if(c=='N')
        {
            dx=-1;
            dy=0;
        }
        if(c=='E')
        {
            dx=0;
            dy=1;
        }
        if(c=='S')
        {
            dx=1;
            dy=0;
        }
        if(c=='W')
        {
            dx=0;
            dy=-1;
        }
        x+=dx;
        y+=dy;
        p[i]={x,y};
        //printf("[%lld,%lld]\n",p[i].first,p[i].second);
        mp[p[i]]=2;
    }
    swap(n,m);
    m=M+1;
    for(i=1;i<=m;i++)
    {
        for(j=0;j<8;j++)
        {
            q={p[i].first+ddx[j],p[i].second+ddy[j]};
            if(mp[q])
                continue;
            mp[q]=1;
            u.push_back(q);
        }
    }
    for(i=0;i<u.size();i++)
    {
       // printf("(%lld %lld %lld)\n",i,u[i].first,u[i].second);
        mpp[u[i]]=i;
    }
    for(i=0;i<u.size();i++)
    {
        x=u[i].first;
        y=u[i].second;
        for(j=0;j<8;j++)
        {
            if(mp[{x+ddx[j],y+ddy[j]}]==1)
                {
                    v[i].push_back(mpp[{x+ddx[j],y+ddy[j]}]);
                }
        }
    }
}
ll ok(pair<ll,ll> p,ll x,ll y,ll z,ll w)
{
    if(x<=p.first&&p.first<=z&&y<=p.second&&p.second<=w)
        return 1;
    else
        return 0;
}
void f(ll x,ll ar,ll ac,ll br,ll bc)
{
    ll i;
    cc[x]=1;
    for(i=0;i<v[x].size();i++)
    {
        if(cc[v[x][i]]==0&&ok(u[v[x][i]],ar,ac,br,bc))
            f(v[x][i],ar,ac,br,bc);
    }
}
int colour(int ar, int ac, int br, int bc) {
    s=0;
    for(i=0;i<u.size();i++)
    {
        if(cc[i]==0&&ok(u[i],ar,ac,br,bc))
        {
           // printf("(%lld,%lld,%lld)\n",i,u[i].first,u[i].second);
            s++;
            f(i,ar,ac,br,bc);
        }
    }
    return s;
}

Compilation message (stderr)

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:68:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(i=0;i<u.size();i++)
      |             ~^~~~~~~~~
rainbow.cpp:73:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for(i=0;i<u.size();i++)
      |             ~^~~~~~~~~
rainbow.cpp: In function 'void f(ll, ll, ll, ll, ll)':
rainbow.cpp:97:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for(i=0;i<v[x].size();i++)
      |             ~^~~~~~~~~~~~
rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:105:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     for(i=0;i<u.size();i++)
      |             ~^~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 12
• Subtask 3: 0 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26