oj.uz

Submission #678668

# Submission time Handle Problem Language Result Execution time Memory
678668 2023-01-06T10:14:47 Z qwerasdfzxcl Land of the Rainbow Gold (APIO17_rainbow) C++17
12 / 100
 79 ms 8768 KB 
#include "rainbow.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
constexpr int INF = 1e9+100;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int dx8[9] = {-1, -1, -1, 0, 1, 1, 1, 0, -1}, dy8[9] = {-1, 0, 1, 1, 1, 0, -1, -1, -1};
set<pair<int, int>> st;
vector<int> S[3], E[3];
int n;

void init(int R, int C, int sr, int sc, int M, char *S) {
    st.emplace(sr, sc);

    for (int i=0;i<M;i++){
        int k;
        if (S[i]=='N') k = 0;
        if (S[i]=='E') k = 1;
        if (S[i]=='S') k = 2;
        if (S[i]=='W') k = 3;

        sr += dx[k], sc += dy[k];
        st.emplace(sr, sc);
    }

    auto iter = st.begin();
    for (int i=1;i<=2;i++){
        int prv = 1;
        while(iter!=st.end() && iter->first==i){
            if (iter->second > prv){
                ::S[i].push_back(prv);
                E[i].push_back(iter->second-1);
                //ran.emplace_back(prv, iter->second-1);
                //printf("ran: %d %d\n", prv, iter->second-1);
            }
            prv = iter->second+1;
            ++iter;
        }

        if (prv<=C){
            ::S[i].push_back(prv);
            E[i].push_back(C);
            //printf("ran: %d %d\n", prv, C);
        }
    }

    n = C;
}

bool valid(int x, int y, int ar, int ac, int br, int bc){
    if (st.find(make_pair(x, y))!=st.end()) return 0;
    return ar <= x && x <= br && ac <= y && y <= bc;
}

void add_edge(int x1, int y1, int x2, int y2, set<pair<int, int>> &V, map<pair<int, int>, vector<pair<int, int>>> &E, int ar, int ac, int br, int bc){
    if (valid(x1, y1, ar, ac, br, bc)) V.emplace(x1, y1);
    if (valid(x2, y2, ar, ac, br, bc)) V.emplace(x2, y2);

    if (!valid(x1, y1, ar, ac, br, bc)) return;
    if (!valid(x2, y2, ar, ac, br, bc)) return;

    auto p1 = make_pair(x1, y1);
    auto p2 = make_pair(x2, y2);
    E[p1].push_back(p2);
    E[p2].push_back(p1);

    //printf("add_edge: %d %d %d %d\n", x1, y1, x2, y2);
}

void dfs(int x, int y, map<pair<int, int>, vector<pair<int, int>>> &E, set<pair<int, int>> &visited){
    visited.emplace(x, y);
    auto p = make_pair(x, y);
    for (auto np:E[p]) if (visited.find(np)==visited.end()){
        dfs(np.first, np.second, E, visited);
    }
}

int colour(int ar, int ac, int br, int bc) {
    int cnt[3];
    for (int i=1;i<=2;i++){
        cnt[i] = (upper_bound(S[i].begin(), S[i].end(), bc) - S[i].begin()) - (lower_bound(E[i].begin(), E[i].end(), ac) - E[i].begin());
        cnt[i] = max(cnt[i], 0);
    }

    if (ar==br) return cnt[ar];
    int ans = cnt[1] + cnt[2];
    if (!S[1].empty() && !S[2].empty()){
        if (S[1][0]==1 && S[2][0]==1 && E[1][0] >= ac && E[2][0] >= ac) ans--;
        if (E[1].back()==n && E[2].back()==n && S[1].back() <= bc && S[2].back() <= bc) ans--;
    }

    return ans;


    /*if (br <= st.begin()->first-1) return 1;
    ar = max(ar, st.begin()->first-1);
    set<pair<int, int>> V, visited;
    map<pair<int, int>, vector<pair<int, int>>> E;

    for (int i=ar;i<=br;i++){
        add_edge(i, ac, i+1, ac, V, E, ar, ac, br, bc);
        add_edge(i, bc, i+1, bc, V, E, ar, ac, br, bc);
    }

    for (int j=ac;j<=bc;j++){
        add_edge(ar, j, ar, j+1, V, E, ar, ac, br, bc);
        add_edge(br, j, br, j+1, V, E, ar, ac, br, bc);
    }

    for (auto [x, y]:st){
        for (int k=0;k<8;k++){
            int nx1 = x + dx8[k], ny1 = y + dy8[k];
            int nx2 = x + dx8[k+1], ny2 = y + dy8[k+1];

            add_edge(nx1, ny1, nx2, ny2, V, E, ar, ac, br, bc);
        }
    }

    int ret = 0;
    for (auto &[x, y]:V) if (visited.find(make_pair(x, y))==visited.end()) {dfs(x, y, E, visited); ret++;}
    return ret;*/
}

Compilation message

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:23:32: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
   23 |         sr += dx[k], sc += dy[k];
      |                            ~~~~^

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 57 ms 6368 KB Output is correct
4 Correct 74 ms 8628 KB Output is correct
5 Correct 79 ms 8672 KB Output is correct
6 Correct 72 ms 8000 KB Output is correct
7 Correct 74 ms 7796 KB Output is correct
8 Correct 50 ms 3904 KB Output is correct
9 Correct 74 ms 8652 KB Output is correct
10 Correct 79 ms 8768 KB Output is correct
11 Correct 71 ms 7976 KB Output is correct
12 Correct 63 ms 8268 KB Output is correct
13 Correct 63 ms 8600 KB Output is correct
14 Correct 64 ms 8652 KB Output is correct
15 Correct 62 ms 8004 KB Output is correct
16 Correct 60 ms 7216 KB Output is correct

Subtask #3
0 / 24.0

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

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -