oj.uz

Submission #775076

# Submission time Handle Problem Language Result Execution time Memory
775076 2023-07-06T07:23:09 Z gagik_2007 Land of the Rainbow Gold (APIO17_rainbow) C++17
11 / 100
 681 ms 1048576 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define ff first
#define ss second

ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=5007;
ll n,m,k;
vector<vector<int>>a;
vector<vector<int>>used;
vector<vector<int>>d;

void init(int R, int C, int sr, int sc, int M, char* SSSSSS) {
    string S=SSSSSS;
    n=R;
    m=C;
    a.resize(n+2, vector<int>(0, 0));
    used.resize(n+2, vector<int>(0, 0));
    d.resize(n+2, vector<int>(0, 0));
    for(int i=0;i<=n+1;i++){
        a[i].resize(m+2, 0);
        used[i].resize(m+2, 0);
        d[i].resize(m+2, 0);
    }
    // cout<<"a: "<<a.size()<<"x"<<a[0].size()<<endl;
    // cout<<a[6][3]<<endl;
    int i=sr,j=sc;
    a[i][j]=1;
    for(int ch:S){
        if(ch=='N'){
            i--;
        }
        if(ch=='E'){
            j++;
        }
        if(ch=='S'){
            i++;
        }
        if(ch=='W'){
            j--;
        }
        a[i][j]=1;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]==0&&a[i][j+1]==1){
                d[i][j]=d[i][j-1]+1;
            }
            else{
                d[i][j]=d[i][j-1];
            }
        }
    }
}

vector<pii>deltas={make_pair(1,0),make_pair(-1,0),make_pair(0,1),make_pair(0,-1)};

void dfs(int i, int j, int mxi, int mni, int mxj, int mnj){
    // cout<<"DFS: "<<i<<" "<<j<<endl;
    used[i][j]=1;
    for(pii delta:deltas){
        int di=delta.ff;
        int dj=delta.ss;
        if(i+di<=mxi&&i+di>=mni&&j+dj<=mxj&&j+dj>=mnj){
            // cout<<"STUG: "<<i+di<<" "<<j+dj<<endl;
            if(!used[i+di][j+dj]&&!a[i+di][j+dj]){
                // cout<<"STUG OK"<<endl;
                dfs(i+di,j+dj,mxi,mni,mxj,mnj);
            }
            // cout<<"STUG EXAV"<<endl;
        }
    }
}

int colour(int ar, int ac, int br, int bc) {
    // cout<<"QUERY: "<<ar<<" "<<ac<<" "<<br<<" "<<bc<<endl;
    if(n<=50&&m<=50){
        int cnt=0;
        for(int i=ar;i<=br;i++){
            for(int j=ac;j<=bc;j++){
                if(!used[i][j]&&!a[i][j]){
                    cnt++;
                    dfs(i,j,br,ar,bc,ac);
                }
            }
        }
        for(int i=ar;i<=br;i++){
            for(int j=ac;j<=bc;j++){
                used[i][j]=0;
            }
        }
        return cnt;
    }
    int cnt=0;
    if(ar==1&&br==2){
        cnt+=d[1][bc]-d[1][ac-1];
        cnt+=d[2][bc]-d[2][ac-1];
        if(a[1][bc]==0&&a[1][bc+1]==0)cnt++;
        if(a[2][bc]==0&&a[2][bc+1]==0)cnt++;
        if(a[1][bc]==0&&a[2][bc]==0)cnt--;
        if(a[1][ac]==0&&a[2][ac]==0)cnt--;
        if(d[1][bc]-d[1][ac-1]==0&&d[2][bc]-d[2][ac-1]==0)cnt++;
    }
    else if(ar==1){
        cnt+=d[1][bc]-d[1][ac-1];
        if(a[1][bc]==0&&a[1][bc+1]==0)cnt++;
    }
    else{
        cnt+=d[2][bc]-d[2][ac-1];
        if(a[2][bc]==0&&a[2][bc+1]==0)cnt++;
    }
    return cnt;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 6 ms 340 KB Output is correct
3 Correct 10 ms 468 KB Output is correct
4 Correct 12 ms 448 KB Output is correct
5 Correct 5 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 304 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 304 KB Output is correct
11 Correct 9 ms 444 KB Output is correct
12 Correct 8 ms 340 KB Output is correct
13 Correct 7 ms 324 KB Output is correct
14 Correct 5 ms 340 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 48 ms 13332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 681 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 6 ms 340 KB Output is correct
3 Correct 10 ms 468 KB Output is correct
4 Correct 12 ms 448 KB Output is correct
5 Correct 5 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 304 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 304 KB Output is correct
11 Correct 9 ms 444 KB Output is correct
12 Correct 8 ms 340 KB Output is correct
13 Correct 7 ms 324 KB Output is correct
14 Correct 5 ms 340 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Incorrect 50 ms 15820 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 6 ms 340 KB Output is correct
3 Correct 10 ms 468 KB Output is correct
4 Correct 12 ms 448 KB Output is correct
5 Correct 5 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 304 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 304 KB Output is correct
11 Correct 9 ms 444 KB Output is correct
12 Correct 8 ms 340 KB Output is correct
13 Correct 7 ms 324 KB Output is correct
14 Correct 5 ms 340 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Incorrect 50 ms 15820 KB Output isn't correct
19 Halted 0 ms 0 KB -