Submission #547326

#	Time	Username	Problem	Language	Result	Execution time	Memory
547326		Victor	Land of the Rainbow Gold (APIO17_rainbow)	C++17	11 / 100	61 ms	3904 KiB

rainbow

// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b) - 1; i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout<<#x<<" = "<<x<<endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

const int INF = 1'000'000'007;

#include "rainbow.h"

int dr[]={1,-1,0,0};
int dc[]={0,0,1,-1};
int rows,cols,AR,AC,BR,BC;
vector<vector<bool>> grid,vis;

bool valid(int row,int col) { return AR<=row&&row<BR&&AC<=col&&col<BC; }

void dfs(int row,int col) {
    vis[row][col]=1;
    //cout<<"row = "<<row<<" col = "<<col<<" grid = "<<grid[row][col]<<endl;
    rep(k,0,4) {
        int nr=row+dr[k],nc=col+dc[k];
        if(valid(nr,nc)&&!vis[nr][nc]&&!grid[nr][nc]) dfs(nr,nc);
    }
}

void init(int R, int C, int sr, int sc, int M, char *S) {
    rows=R;
    cols=C;
    --sr; --sc;

    rep(i,0,M) {
        if(S[i]=='S') S[i]=0;
        if(S[i]=='N') S[i]=1;
        if(S[i]=='E') S[i]=2;
        if(S[i]=='W') S[i]=3;
    }

    if(rows<=50&&cols<=50) {
        grid.assign(R,vector<bool>(C,0));
        grid[sr][sc]=1;

        rep(i,0,M) {
            sr+=dr[S[i]];
            sc+=dc[S[i]];
            grid[sr][sc]=1;
        }

        //rep(i,0,rows) {
        //    rep(j,0,cols) cout<<grid[i][j]<<' ';
        //    cout<<endl;
        //}
        //cout<<endl;
    }
}

int colour(int ar, int ac, int br, int bc) {
    int ans=0;
    if(rows<=50&&cols<=50) {
        --ar; --ac;
        AR=ar;
        AC=ac;
        BR=br;
        BC=bc;

        vis.assign(rows,vector<bool>(cols,0));
        rep(i,ar,br) { 
            rep(j,ac,bc) {
                if(vis[i][j]||grid[i][j]) continue;
                ++ans;
                dfs(i,j);
            }
        }
    }
    return ans;
}

/*
#include "rainbow.h"

#include <stdio.h>

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 'void init(int, int, int, int, int, char*)':
rainbow.cpp:68:23: warning: array subscript has type 'char' [-Wchar-subscripts]
   68 |             sr+=dr[S[i]];
      |                    ~~~^
rainbow.cpp:69:23: warning: array subscript has type 'char' [-Wchar-subscripts]
   69 |             sc+=dc[S[i]];
      |                    ~~~^

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