#include "rainbow.h"
#include <iostream>
#include <assert.h>
#include <queue>
using namespace std;
bool B[3][200005];
bool V[3][200005];
int R,C;
int A[3][200005];
int P[3][2][200005];
bool B_old[55][55];
bool V_old[55][55];
int rmov[]={1,-1,0,0};
int cmov[]={0,0,1,-1};
queue<pair<int,int>> Q;
void init(int R_, int C_, int sr, int sc, int M, char *W) {
R=R_;
C=C_;
if(R<51 and C<51){
B_old[sr][sc]=true;
for(int i=0;i<M;i++){
if(W[i]=='S')
sr++;
if(W[i]=='N')
sr--;
if(W[i]=='E')
sc++;
if(W[i]=='W')
sc--;
B_old[sr][sc]=true;
}
return;
}
B[1][0]=B[2][0]=true;
B[1][C+1]=B[2][C+1]=false;
B[1][C+2]=B[2][C+2]=true;
for(int k=0;k<3;k++){
A[k][0]=-1;
P[k][0][0]=-1;
P[k][0][C+2]=-1;
P[k][1][0]=-1;
P[k][1][C+2]=-1;
}
B[sr][sc]=true;
int cont=0;
for(int i=0;i<M;i++){
if(W[i]=='S')
sr++;
if(W[i]=='N')
sr--;
if(W[i]=='E')
sc++;
if(W[i]=='W')
sc--;
B[sr][sc]=true;
}
for(int r=1;r<R+1;r++)
for(int i=1;i<C+3;i++)
if(B[r][i] and !B[r][i-1])
A[r-1][i]=-1;
else if(!B[r][i] and B[r][i-1])
A[r-1][i]=++cont;
else
A[r-1][i]=A[r-1][i-1];
for(int i=1;i<C+3;i++)
if((B[2][i]&B[1][i]) and !(B[2][i-1]&B[1][i-1]))
A[2][i]=-1;
else if(!(B[2][i]&B[1][i]) and (B[2][i-1]&B[1][i-1]))
A[2][i]=++cont;
else
A[2][i]=A[2][i-1];
for(int k=0;k<3;k++){
for(int i=1;i<C+3;i++)
P[k][0][i]=(A[k][i]==-1)?P[k][0][i-1]:A[k][i];
for(int i=C+1;i>=0;i--)
P[k][1][i]=(A[k][i]==-1)?P[k][1][i+1]:A[k][i];
}
for(int k=0;k<3;k++){
int res;
for(int i=C+1;i>=0;i--)
if(P[k][0][i]==-1 and P[k][0][i+1]!=-1)
res=P[k][0][i+1]-1;
for(int i=C+1;i>=0;i--)
if(P[k][0][i]==-1)
P[k][0][i]=res;
}
/*
for(int k=0;k<3;k++){
for(int i=0;i<C+3;i++)
cout<<A[k][i]<<" ";
cout<<endl;
}
for(int k=0;k<3;k++){
for(int i=0;i<C+3;i++)
cout<<P[k][0][i]<<" ";
cout<<endl;
}
for(int k=0;k<3;k++){
for(int i=0;i<C+3;i++)
cout<<P[k][1][i]<<" ";
cout<<endl;
}*/
}
int colour(int ar, int ac, int br, int bc) {
if(R<51 and C<51){
ar--;
ac--;
br--;
bc--;
int ans=0;
for(int i=0;i<R;i++)
for(int j=0;j<C;j++)
V_old[i][j]=B_old[i][j];
for(int i=ar;i<=br;i++)
for(int j=ac;j<=bc;j++)
if(!V_old[i][j]){
ans++;
while(Q.size())
Q.pop();
Q.push({i,j});
while(Q.size()){
pair<int,int> p=Q.front();
Q.pop();
if(V_old[p.first][p.second])
continue;
V_old[p.first][p.second]=true;
for(int m=0;m<4;m++)
if(!V_old[p.first+rmov[m]][p.second+cmov[m]] and ar<=p.first+rmov[m] and p.first+rmov[m]<=br and ac<=p.second+cmov[m] and p.second+cmov[m]<=bc)
Q.push({p.first+rmov[m],p.second+cmov[m]});
}
}
return ans;
}
int k;
if(ar==1 and br==1)
k=0;
else if(ar==2 and br==2)
k=1;
else if(ar==1 and br==2)
k=2;
else
assert(false);
return P[k][0][bc]-P[k][1][ac]+1;
}
Compilation message
rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:105:15: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
P[k][0][i]=res;
~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
432 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
