Submission #57353

#TimeUsernameProblemLanguageResultExecution timeMemory
57353MatheusLealVLand of the Rainbow Gold (APIO17_rainbow)C++17
12 / 100
195 ms6364 KiB
#include "rainbow.h" #include <bits/stdc++.h> #define N 200050 #define f first #define s second using namespace std; typedef pair<int, int> pii; int n, m, ok[5][N], block[5][N]; int inicio[5][N]; int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1}; int Ni, Mi, Nii, Mii, col; int branco[2][N]; int dxy(char c) { if(c == 'N') return 1; if(c == 'S') return 0; if(c == 'W') return 3; if(c == 'E') return 2; return -1; } int pref[5][N]; void dfs(int x, int y) { ok[x][y] = 1; //cout<<"DFS "<<x<<" "<<y<<"\n"; for(int i = 0; i < 4; i++) { int a = x + dx[i], b = y + dy[i]; if(a < Ni or b < Mi or a > Nii or b > Mii or ok[a][b] == 1 or block[a][b]) continue; ok[a][b] = 1; dfs(a, b); } } vector < pii > zeros; int ans[5][N]; int colmin = N, colmax = 0; void init(int R, int C, int sr, int sc, int M, char *S) { int x = sr, y = sc; col = C; string s; block[x][y] = 1; for(int i = 0; i < M; i++) s.push_back(S[i]); for(int i = 0; i < s.size(); i++) { block[x][y] = 1; int id = dxy(s[i]); if(id == -1) break; x = x + dx[id], y = y + dy[id]; block[x][y] = 1; //cout<<"BLOCK "<<s.size()<<" "<<x<<" "<<y<<"\n"; } for(int i = 1; i <= 2; i++) for(int j = 1; j <= C; j++) pref[i][j] = pref[i][j - 1] + block[i][j]; for(int i = 1; i <= 2; i++) { for(int j = 1; j <= C; j++) { if(block[i][j]) pref[i][j] = pref[i][j - 1]; else pref[i][j] = 1 + pref[i][j - 1]; } } for(int i = 1; i <= 2; i++) { for(int j = 1; j <= C; j++) { int st = j, entrou = 0; while(!block[i][j] and j <= C) j++, entrou = 1; if(entrou) j--; if(!block[i][st]) { zeros.push_back({st, j}); ans[i][st] ++; inicio[i][st] = 1; //cout<<"ADD "<<i<<", "<<st<<"\n"; //ans[i][j] --; } } } for(int i = 1; i <= 2; i++) for(int j = 1; j <= col; j++) ans[i][j] += ans[i][j - 1]; for(int i = 1; i <= 2; i++) { for(int j = 1; j <= C; j++) { if(block[i][j] == 1) { colmax = max(colmax, j); colmin = min(colmin, j); } } } } int colour(int ar, int ac, int br, int bc) { int cnt = 0; if(ar == br) { if(!block[ar][ac - 1] and ac > 1 and !block[ar][ac ]) return 1 + ans[ar][bc] - ans[ar][ac - 1]; else return ans[ar][bc] - ans[ar][ac - 1]; } else { int dA = 0, dB = 0; if(block[1][colmin] and block[2][colmin] and ac < colmin) dA ++; if(block[1][colmax] and block[2][colmax] and bc > colmax) dB ++; //cout<<"DELTA "<<dA<<" "<<dB<<'\n'; ac = max(ac, colmin); bc = min(bc, colmax); if(!block[1][ac - 1] and ac > 1 and !block[1][ac ]) dA += 1 + ans[1][bc] - ans[1][ac - 1]; else dA += ans[1][bc] - ans[1][ac - 1]; // cout<<"DELTA LINHA 1 "<<colmin<<" "<<colmax<<" "<<dA<<"\n"; if(!block[2][ac - 1] and ac > 1 and !block[2][ac ]) dA += 1 + ans[2][bc] - ans[2][ac - 1]; else dA += ans[2][bc] - ans[2][ac - 1]; /// cout<<"DELTA LINHA 2 "<<colmin<<" "<<colmax<<" "<<dA<<"\n"; return dA + dB; } }

Compilation message (stderr)

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:70:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < s.size(); i++)
                 ~~^~~~~~~~~~
rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:143:9: warning: unused variable 'cnt' [-Wunused-variable]
     int cnt = 0;
         ^~~
#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...