#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);
}
prv = iter->second+1;
++iter;
}
if (prv<=C){
::S[i].push_back(prv);
E[i].push_back(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) - lower_bound(E[i].begin(), E[i].end(), ac);
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[1][1] >= ac) ans--;
if (E[1].back()==n && E[2].back()==n && S[1].back() <= bc && E[1].back() <= bc) ans--;
if (S[1][0]==1 && S[2][0]==1 && E[1][0]==n && E[2][0]==n) 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];
| ~~~~^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
244 KB |
Output is correct |
| 2 |
Incorrect |
18 ms |
5020 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
