Submission #1117130

#TimeUsernameProblemLanguageResultExecution timeMemory
1117130gustavo_dLand of the Rainbow Gold (APIO17_rainbow)C++17
0 / 100
17 ms592 KiB
#include "rainbow.h" #include <bits/stdc++.h> using namespace std; map<char, pair<int, int>> ds; pair<int, int> moves[4] = { {0, -1}, {0, 1}, {1, 0}, {-1, 0}, }; bool mark[51][51]; bool mark2[3][200001]; int x, y; // TODO: cout de debug que some ao submeter vector<pair<int, int>> r1, r2, r12; void init(int R, int C, int sr, int sc, int M, char *S) { x=R; y=C; ds['N'] = {-1, 0}; ds['S'] = {1, 0}; ds['E'] = {0, 1}; ds['W'] = {0, -1}; if (R == 2) { mark2[sr][sc] = true; // cout << sr << ' ' << sc << endl; for (int i=0; i<M; i++) { char c = S[i]; sr += ds[c].first; sc += ds[c].second; mark2[sr][sc] = true; // cout << sr << ' ' << sc << endl; } pair<int, int> rng = {-1, -1}; for (int i=1; i<=C; i++) { if (mark2[1][i]) { if (rng.first != -1) { r1.push_back(rng); } rng = {-1, -1}; } else { if (rng.first == -1) rng = {i, i}; else rng.second++; } } if (rng.first != -1) { // cout << "1: " << rng.first << ' ' << rng.second << '\n'; r1.push_back(rng); } rng = {-1, -1}; for (int i=1; i<=C; i++) { if (mark2[2][i]) { if (rng.first != -1) { r2.push_back(rng); } rng = {-1, -1}; } else { if (rng.first == -1) rng = {i, i}; else rng.second++; } } if (rng.first != -1) { // cout << "2: " << rng.first << ' ' << rng.second << '\n'; r2.push_back(rng); } rng = {-1, -1}; for (int i=1; i<=C; i++) { if (!mark2[1][i] or !mark2[2][i]) { if (rng.first != -1) { r12.push_back(rng); } rng = {-1, -1}; } else { if (rng.first == -1) rng = {i, i}; else rng.second++; } } if (rng.first != -1) { // cout << "1, 2: " << rng.first << ' ' << rng.second << '\n'; r12.push_back(rng); } return; } for (int i=0; i<=50; i++) mark[i][0] = true; for (int i=0; i<=50; i++) mark[0][i] = true; mark[sr][sc] = true; // cout << sr << ' ' << sc << endl; for (int i=0; i<M; i++) { char c = S[i]; sr += ds[c].first; sc += ds[c].second; mark[sr][sc] = true; // cout << sr << ' ' << sc << endl; } } bool tmp[51][51]; int lar, lac, lbr, lbc; void dfs(int i, int j) { if (i < lar or j < lac or i > lbr or j > lbc or tmp[i][j]) return; tmp[i][j] = true; for (pair<int, int> d : moves) { dfs(i + d.first, j + d.second); } } int solve(vector<pair<int, int>> &rngs, int l, int r) { auto fi = lower_bound(rngs.begin(), rngs.end(), make_pair(l, 0)); if (fi != rngs.begin()) { fi--; if ((fi->second) < l) fi++; } if (fi == rngs.end()) return 0; auto last = upper_bound(rngs.begin(), rngs.end(), make_pair(r, (int)1e9)); if (last == rngs.begin()) return 0; last--; return distance(fi, last) + 1; } int colour(int ar, int ac, int br, int bc) { if (x == 2) { if (ar == 1 and br == 1) { // cout << "caso 1" << endl; return solve(r1, ac, bc); } if (ar == 2 and br == 2) { // cout << "caso 2" << endl; return solve(r2, ac, bc); } if (ar == 1 and br == 2) { // cout << "caso 1, 2" << endl; return solve(r12, ac, bc); } } lar = ar; lac = ac; lbr = br; lbc = bc; int cnt = 0; for (int i=1; i<=50; i++) { for (int j=1; j<=50; j++) { tmp[i][j] = mark[i][j]; } } for (int r=ar; r<=br; r++) { for (int c=ac; c<=bc; c++) { if (!tmp[r][c]) { cnt++; dfs(r, c); } } } return cnt; }
#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...