Submission #569422

#TimeUsernameProblemLanguageResultExecution timeMemory
569422Ooops_sorryLand of the Rainbow Gold (APIO17_rainbow)C++14
0 / 100
3042 ms5068 KiB
#include<bits/stdc++.h> #ifndef LOCAL #include "rainbow.h" #endif // LCOAL using namespace std; #define pb push_back #define ld double #define ll long long mt19937 rnd(51); set<pair<int,int>> st; vector<pair<int,int>> d{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; void init(int r, int c, int sr, int sc, int m, char *s) { st.clear(); sr--, sc--; st.insert({sr, sc}); for (int i = 0; i < m; i++) { if (s[i] == 'N') { sr--; } else if (s[i] == 'S') { sr++; } else if (s[i] == 'W') { sc--; } else { sc++; } assert(0 <= sr && sr < r && 0 <= sc && sc < c); st.insert({sr, sc}); } } bool check(int i, int j) { return (st.find({i, j}) != st.end()); } int colour(int ar, int ac, int br, int bc) { ar--, ac--, br--, bc--; ll n = 0, m = 0, s = 0; for (int i = ar; i <= br; i++) { for (int j = ac; j <= bc; j++) { if (check(i, j)) { n++; if (i + 1 <= br && check(i + 1, j)) { m++; } if (j + 1 <= bc && check(i, j + 1)) { m++; } if (i + 1 <= br && j + 1 <= bc && check(i + 1, j + 1) && check(i, j + 1) && check(i + 1, j)) { s++; } } } } if (n == (ll)(br - ar + 1) * (bc - ac + 1)) { return 0; } int cnt = 0; for (int i = ar; i <= br; i++) { if (check(i, ac)) { cnt++; if (i + 1 <= br && check(i + 1, ac)) { s++; } } if (check(i, bc)) { cnt++; if (i + 1 <= br && check(i + 1, bc)) { s++; } } } for (int j = ac; j <= bc; j++) { if (check(ar, j)) { cnt++; if (j + 1 <= bc && check(ar, j + 1)) { s++; } } if (check(br, j)) { cnt++; if (j + 1 <= bc && check(br, j + 1)) { s++; } } } if (cnt == 0) { if (n == 0) { return 1; } else { return 2 + m - n; } } else { m += cnt; vector<pair<int,int>> st; if (check(ar, ac)) s++; if (check(ar, bc)) s++; if (check(br, ac)) s++; if (check(br, bc)) s++; return 1 + m - n - s; } } int solve(int ar, int ac, int br, int bc) { ar--, ac--, br--, bc--; map<pair<int,int>, int> used; int cnt = 0; for (int i = ar; i <= br; i++) { for (int j = ac; j <= bc; j++) { if (!check(i, j) && !used[{i, j}]) { cnt++; used[{i, j}] = 1; deque<pair<int,int>> q{{i, j}}; while (q.size() > 0) { int f = q.front().first, s = q.front().second; q.pop_front(); for (auto to : d) { f += to.first, s += to.second; if (ar <= f && f <= br && ac <= s && s <= bc) { if (!used[{f, s}] && !check(f, s)) { q.pb({f, s}); used[{f, s}] = 1; } } f -= to.first, s -= to.second; } } } } } return cnt; } #ifdef LOCAL static int R, C, M, Q; static int sr, sc; static char S[100000 + 5]; int main() { vector<char> LOL{{'N', 'S', 'W', 'E'}}; int MX = 3; while (1) { int r = rnd() % MX + 1, c = rnd() % MX + 1, m = rnd() % MX + 1, q = rnd() % MX + 1; char s[m]; for (int i = 0; i < m; i++) { s[i] = LOL[rnd() % 4]; } int x = rnd() % r, y = rnd() % c; int sr = x, sc = y; bool bad = 0; for (int i = 0; i < m; i++) { if (s[i] == 'N') { sr--; } else if (s[i] == 'S') { sr++; } else if (s[i] == 'W') { sc--; } else { sc++; } if (!(0 <= sr && sr < r && 0 <= sc && sc < c)) { bad = 1; break; } } if (bad) continue; init(r, c, x + 1, y + 1, m, s); for (int i = 0; i < q; i++) { int ar = rnd() % r, br = rnd() % r, ac = rnd() % c, bc = rnd() % c; if (ar > br) swap(ar, br); if (ac > bc) swap(ac, bc); auto res = solve(ar + 1, ac + 1, br + 1, bc + 1), res2 = colour(ar + 1, ac + 1, br + 1, bc + 1); if (res != res2) { cout << "BAD" << endl; cout << r << ' ' << c << ' ' << m << ' ' << endl; cout << x << ' ' << y << endl; for (int i = 0; i < m; i++) { cout << s[i]; } cout << endl; cout << ar << ' ' << ac << ' ' << br << ' ' << bc << endl; cout << res << ' ' << res2 << endl; return 0; } } cout << "OK" << endl; } 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; } #endif // LOCAL
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...