#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
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++)
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
29276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
29272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
29276 KB |
Output is correct |
| 2 |
Correct |
509 ms |
84980 KB |
Output is correct |
| 3 |
Correct |
400 ms |
84924 KB |
Output is correct |
| 4 |
Correct |
443 ms |
89276 KB |
Output is correct |
| 5 |
Correct |
330 ms |
70556 KB |
Output is correct |
| 6 |
Incorrect |
64 ms |
32944 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
29276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
29276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
