Submission #910905

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

rainbow

/*#include "rainbow.h"
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
void init(int R, int C, int sr, int sc, int M, char *S) {
    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];
        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};
        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;
            v.push_back(q);
        }
    }
    for(i=0;i<v.size();i++)
    {
        q=v[i];
        if(c[q])
            continue;
        while(1)
        {
            if(c[q]==1)
                break;
            c[q]=1;
            add(q);
        x=mp[{q.first-1,q.second}];
        y=mp[{q.first,q.second+1}];
        z=mp[{q.first+1,q.second}];
        w=mp[{q.first,q.second-1}];
        x=f(x);  y=f(y);  z=f(z);  w=f(w);
        dx=px[x][y][z][w][prv];
        dy=py[x][y][z][w][prv];
        prv=pp[x][y][z][w][prv];
        pq={q.first+dx,q.second+dy};
        add_edge(q,pq);
        q=pq;
        }
    }
}
int colour(int ar, int ac, int br, int bc) {
    l=ar;
    r=ac;
    return g1(1,262144,1,br,bc)-g2(1,262144,1,br,bc);
}
*/
#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],dddx[11000],dddy[110000];
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;
    }
    dddx[0]=1;  dddy[0]=0;
    dddx[1]=-1; dddy[1]=0;
    dddx[2]=0;
    dddy[2]=1;
    dddx[3]=0;
    dddy[3]=-1;
    for(i=0;i<u.size();i++)
    {
        x=u[i].first;
        y=u[i].second;
        for(j=0;j<4;j++)
        {
            if(mp[{x+dddx[j],y+dddy[j]}]==1)
                {
                    v[i].push_back(mpp[{x+dddx[j],y+dddy[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++)
    {
        cc[i]=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:151: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]
  151 |     for(i=0;i<u.size();i++)
      |             ~^~~~~~~~~
rainbow.cpp:162: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]
  162 |     for(i=0;i<u.size();i++)
      |             ~^~~~~~~~~
rainbow.cpp: In function 'void f(ll, ll, ll, ll, ll)':
rainbow.cpp:186:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  186 |     for(i=0;i<v[x].size();i++)
      |             ~^~~~~~~~~~~~
rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:194: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]
  194 |     for(i=0;i<u.size();i++)
      |             ~^~~~~~~~~
rainbow.cpp:198: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]
  198 |     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