Submission #547333

#TimeUsernameProblemLanguageResultExecution timeMemory
547333VictorLand of the Rainbow Gold (APIO17_rainbow)C++17
Compilation error
0 ms0 KiB
// #pragma GCC target ("avx,avx2,fma") // #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast // #pragma GCC optimize ("unroll-loops") #include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i = (a); i < (b); ++i) #define per(i, a, b) for (int i = (b)-1; i >= (a); --i) #define trav(a, x) for (auto &a : x) #define all(x) x.begin(), x.end() #define sz(x) x.size() #define pb push_back #define debug(x) cout << #x << " = " << x << endl #define umap unordered_map #define uset unordered_set typedef pair<int, int> ii; typedef pair<int, ii> iii; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<vi> vvi; typedef long long ll; typedef pair<ll, ll> pll; typedef vector<ll> vll; typedef vector<pll> vpll; const int INF = 1'000'000'007; #include "rainbow.h" int dr[] = {1, -1, 0, 0}; int dc[] = {0, 0, 1, -1}; int rows, cols, AR, AC, BR, BC,min_col,max_col; bool yes=0; vii segments[3]; vector<vector<bool>> grid, vis; bool valid(int row, int col) { return AR <= row && row < BR && AC <= col && col < BC; } void dfs(int row, int col) { vis[row][col] = 1; if(yes) { min_col=min(min_col,col); max_col=max(max_col,col); } // cout<<"row = "<<row<<" col = "<<col<<" grid = "<<grid[row][col]<<endl; rep(k, 0, 4) { int nr = row + dr[k], nc = col + dc[k]; if (valid(nr, nc) && !vis[nr][nc] && !grid[nr][nc]) dfs(nr, nc); } } void init(int R, int C, int sr, int sc, int M, char *S) { rows = R; cols = C; --sr; --sc; rep(i, 0, M) { if (S[i] == 'S') S[i] = 0; if (S[i] == 'N') S[i] = 1; if (S[i] == 'E') S[i] = 2; if (S[i] == 'W') S[i] = 3; } if (rows <= 50 && cols <= 50 || rows == 2) { grid.assign(R, vector<bool>(C, 0)); grid[sr][sc] = 1; rep(i, 0, M) { sr += dr[S[i]]; sc += dc[S[i]]; grid[sr][sc] = 1; } // rep(i,0,rows) { // rep(j,0,cols) cout<<grid[i][j]<<' '; // cout<<endl; // } // cout<<endl; } if (rows == 2) { yes=1; AC=0; BC=rows; rep(k, 0, 3) { segments[k].emplace_back(-1,-1); if(!k) { AR=0; BR=1; } if(k==1) { AR=1; BR=2; } if(k==2) { AR=0; BR=2; } vis.assign(rows, vector<bool>(cols, 0)); rep(i, AR, BR) { rep(j, AC, BC) { if (vis[i][j] || grid[i][j]) continue; min_col=INF; max_col=0; dfs(i, j); segments[k].emplace_back(min_col,max_col); } } } yes=0; } } int colour(int ar, int ac, int br, int bc) { int ans = 0; if (rows <= 50 && cols <= 50) { --ar; --ac; AR = ar; AC = ac; BR = br; BC = bc; vis.assign(rows, vector<bool>(cols, 0)); rep(i, ar, br) { rep(j, ac, bc) { if (vis[i][j] || grid[i][j]) continue; ++ans; dfs(i, j); } } } else if(rows==2) { int k=0; if(br==2) k=2-ar; auto it_left=upper_bound(all(segments[k]),ii(ac,INF)); if(it_left!=segments[k].begin()) { --it_left; if(it_left->second<ac) ++it_left; } auto it_right=upper_bound(all(segments[k]),ii(bc,INF)); --it_right; int lpos=it_left-segments[k].begin(); int rpos=it_right-segments[k].begin(); ans=max(0,rpos-lpos+1); } return ans; } #include <stdio.h> #include "rainbow.h" static int R, C, M, Q; static int sr, sc; static char S[100000 + 5]; int main() { 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; }

Compilation message (stderr)

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:70:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   70 |     if (rows <= 50 && cols <= 50 || rows == 2) {
      |         ~~~~~~~~~~~^~~~~~~~~~~~~
rainbow.cpp:75:25: warning: array subscript has type 'char' [-Wchar-subscripts]
   75 |             sr += dr[S[i]];
      |                      ~~~^
rainbow.cpp:76:25: warning: array subscript has type 'char' [-Wchar-subscripts]
   76 |             sc += dc[S[i]];
      |                      ~~~^
rainbow.cpp: In function 'int main()':
rainbow.cpp:169:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  169 |     scanf("%d %d %d %d", &R, &C, &M, &Q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
rainbow.cpp:170:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  170 |     scanf("%d %d", &sr, &sc);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
rainbow.cpp:172:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  172 |         scanf(" %s ", S);
      |         ~~~~~^~~~~~~~~~~
rainbow.cpp:180:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  180 |         scanf("%d %d %d %d", &ar, &ac, &br, &bc);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccvQ9dOT.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccN4rj1Q.o:rainbow.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status