Submission #200321

#	Time	Username	Problem	Language	Result	Execution time	Memory
200321		Nordway	Land of the Rainbow Gold (APIO17_rainbow)	C++14	23 / 100	88 ms	4796 KiB

rainbow

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

#define x first
#define y second
#define pb push_back
#define sz(v) (int)v.size()

using namespace std;

const int N=1e3+11;
const int M=2e5+11;
const int dx[4]={0,0,-1,1};
const int dy[4]={1,-1,0,0};

int n,m;
int x,y;
string s;
bool used[N][N];
bool us[3][M];
int cnt[M],p[3][M];
int msk[M];

void init(int R, int C, int sr, int sc, int M, char* S) {
  n=R;
  m=C;
  x=sr,y=sc;
  s=S;
  if(n==2){
    us[1][0]=1;
    us[2][0]=1;
    us[sr][sc]=1;
    for(int i=0;i<sz(s);i++){
      if(s[i]=='N')sr--;
      if(s[i]=='S')sr++;
      if(s[i]=='W')sc--;
      if(s[i]=='E')sc++;
      us[sr][sc]=1;
    }
    int lst=0;
    msk[0]=lst;
    for(int i=1;i<=m;i++){
      int cur=3;
      for(int j=1;j<=2;j++){
        if(us[j][i])cur^=(1<<(j-1));
      }
      msk[i]=cur;
      if((lst&cur)==0&&cur>0)cnt[i]=cnt[i-1]+1;
      else cnt[i]=cnt[i-1];
      lst=cur;
    }
    for(int i=1;i<=2;i++){
      for(int j=1;j<=m;j++){
        if(us[i][j]==1)p[i][j]=p[i][j-1];
        else if(us[i][j-1]==0&&j>1)p[i][j]=p[i][j-1];
        else p[i][j]=p[i][j-1]+1;
      }
    }
  }
}

void dfs(int r,int c){
  used[r][c]=1;
  //cout<<r<<" "<<c<<endl;
  for(int i=0;i<4;i++){
    int nx=r+dx[i],ny=c+dy[i];
    if(used[nx][ny])continue;
    dfs(nx,ny);
  }
}

int colour(int ar, int ac, int br, int bc) {
  if(n==2){
    if(ar==br){
      return p[ar][bc]-p[ar][ac-1]+(us[ar][ac]==0&&us[ar][ac-1]==0);
    }
    else{
      return cnt[bc]-cnt[ac-1]+((msk[ac]&msk[ac-1])!=0);
    }
  }
  else if(max(n,m)<=50){
    int ans=0;
    for(int i=0;i<=n+1;i++){
      for(int j=0;j<=m+1;j++){
        if(ar<=i&&i<=br&&ac<=j&&j<=bc){
          used[i][j]=0;
          continue;
        }
        used[i][j]=1;
      }
    }
    int sr=x,sc=y;
    used[sr][sc]=1;
    for(int i=0;i<sz(s);i++){
      if(s[i]=='N')sr--;
      if(s[i]=='S')sr++;
      if(s[i]=='W')sc--;
      if(s[i]=='E')sc++;
      used[sr][sc]=1;
    }

    for(int i=ar;i<=br;i++){
      for(int j=ac;j<=bc;j++){
        if(!used[i][j]){
          dfs(i,j);
          //cout<<endl;
          ans++;
        }
      }
    }
    return ans;
  }
}

/*static int R, C, M, Q;
static int sr, sc;
static char S[100000 + 5];

int main() {
    scanf("%d %d %d %d", &R, &C, &M, &Q);
    scanf("%d %d", &sr, &sc);
    if (M > 0) {
        scanf(" %s ", S);
    }

    init(R, C, sr, sc, M, S);

    int query;
    for (query = 0; query < Q; query++) {
        int ar, ac, br, bc;
        scanf("%d %d %d %d", &ar, &ac, &br, &bc);
        printf("%d\n", colour(ar, ac, br, bc));
    }

    return 0;
}*/

Compilation message (stderr)

rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:113:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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