Submission #1089992

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089992		alexander707070	Land of the Rainbow Gold (APIO17_rainbow)	C++14	24 / 100	1399 ms	258060 KiB

rainbow

#include<bits/stdc++.h>
#include "rainbow.h"

#define MAXN 300007
using namespace std;

int n,m,sx,sy,a,b,c,d,x,y,comps;
string w;

map< pair<int,int> , int > mp;

int table[5][MAXN];

void dfs2(int x,int y){
    table[x][y]=comps;

    if(x>1 and table[x-1][y]==0)dfs2(x-1,y);
    if(x<n and table[x+1][y]==0)dfs2(x+1,y);
    if(y>1 and table[x][y-1]==0)dfs2(x,y-1);
    if(y<m and table[x][y+1]==0)dfs2(x,y+1);
}

void precalc(){
    x=sx; y=sy; table[x][y]=-1;
    for(int i=0;i<w.size();i++){
        if(w[i]=='N')x--;
        if(w[i]=='E')y++;
        if(w[i]=='S')x++;
        if(w[i]=='W')y--;
        table[x][y]=-1;
    }

    for(int f=1;f<=m;f++){
        for(int i=1;i<=n;i++){
            if(table[i][f]==0){
                comps++; dfs2(i,f);
            }
        }
    }
}

int pref[MAXN],suff[MAXN];

void init(int R, int C, int sr, int sc, int M, char *S) {
    n=R; m=C;
    sx=sr; sy=sc;

    for(int i=0;i<M;i++){
        w.push_back(S[i]);
    }

    if(n==2){
        precalc();

        for(int i=1;i<=m;i++){
            pref[i]=max(max(table[1][i],table[2][i]),pref[i-1]);
        }

        suff[m+1]=comps+1;
        for(int i=m;i>=1;i--){
            if(table[1][i]==-1)table[1][i]=comps+1;
            if(table[2][i]==-1)table[2][i]=comps+1;

            suff[i]=min(min(table[1][i],table[2][i]),suff[i+1]);
        }
    }
}

bool in(int x,int y){
    return x>=a and x<=c and y>=b and y<=d;
}

void check(int x,int y){
    if(in(x-1,y) and mp[{x-1,y}]==0)mp[{x-1,y}]=1;
    if(in(x+1,y) and mp[{x+1,y}]==0)mp[{x+1,y}]=1;
    if(in(x,y-1) and mp[{x,y-1}]==0)mp[{x,y-1}]=1;
    if(in(x,y+1) and mp[{x,y+1}]==0)mp[{x,y+1}]=1;

    if(in(x-1,y-1) and mp[{x-1,y-1}]==0)mp[{x-1,y-1}]=1;
    if(in(x+1,y+1) and mp[{x+1,y+1}]==0)mp[{x+1,y+1}]=1;
    if(in(x+1,y-1) and mp[{x+1,y-1}]==0)mp[{x+1,y-1}]=1;
    if(in(x-1,y+1) and mp[{x-1,y+1}]==0)mp[{x-1,y+1}]=1;
}

void dfs(int x,int y){
    mp[{x,y}]=2;

    if(mp[{x-1,y}]==1)dfs(x-1,y);
    if(mp[{x+1,y}]==1)dfs(x+1,y);
    if(mp[{x,y-1}]==1)dfs(x,y-1);
    if(mp[{x,y+1}]==1)dfs(x,y+1);
}

void calc(int x,int y){
    if(mp[{x-1,y}]==1){dfs(x-1,y);comps++;}
    if(mp[{x+1,y}]==1){dfs(x+1,y);comps++;}
    if(mp[{x,y-1}]==1){dfs(x,y-1);comps++;}
    if(mp[{x,y+1}]==1){dfs(x,y+1);comps++;}
}

int colour(int ar, int ac, int br, int bc){
    a=ar; b=ac;
    c=br; d=bc;

    if(n==2){
        return pref[bc]-suff[ac]+1;
    }

    comps=0; mp.clear();

    for(int i=a;i<=c;i++){
        mp[{i,b}]=mp[{i,d}]=1;
    }

    for(int i=b;i<=d;i++){
        mp[{a,i}]=mp[{c,i}]=1;
    }

    x=sx; y=sy; mp[{x,y}]=-1;
    for(int i=0;i<w.size();i++){
        if(w[i]=='N')x--;
        if(w[i]=='E')y++;
        if(w[i]=='S')x++;
        if(w[i]=='W')y--;
        mp[{x,y}]=-1;
    }

    x=sx; y=sy; check(x,y);
    for(int i=0;i<w.size();i++){
        if(w[i]=='N')x--;
        if(w[i]=='E')y++;
        if(w[i]=='S')x++;
        if(w[i]=='W')y--;
        check(x,y);
    }

    x=sx; y=sy; calc(x,y);
    for(int i=0;i<w.size();i++){
        if(w[i]=='N')x--;
        if(w[i]=='E')y++;
        if(w[i]=='S')x++;
        if(w[i]=='W')y--;
        calc(x,y);
    }

    if(comps==0 and mp[{a,b}]==1)comps++;

    return comps;
}

/*int main(){

    init(2, 10 ,2,2, 11,"NEEESEENEEE");

    cout<<colour(1,2,2,7)<<"\n";

    return 0;
}*/

Compilation message (stderr)

rainbow.cpp: In function 'void precalc()':
rainbow.cpp:25:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(int i=0;i<w.size();i++){
      |                 ~^~~~~~~~~
rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:120:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     for(int i=0;i<w.size();i++){
      |                 ~^~~~~~~~~
rainbow.cpp:129:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |     for(int i=0;i<w.size();i++){
      |                 ~^~~~~~~~~
rainbow.cpp:138:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |     for(int i=0;i<w.size();i++){
      |                 ~^~~~~~~~~

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