Submission #1045902

#TimeUsernameProblemLanguageResultExecution timeMemory
1045902c2zi6Toy (CEOI24_toy)C++14
0 / 100
46 ms1036 KiB
#define _USE_MATH_DEFINES #include <bits/stdc++.h> #define ff first #define ss second #define pb push_back #define all(a) (a).begin(), (a).end() #define replr(i, a, b) for (int i = int(a); i <= int(b); ++i) #define reprl(i, a, b) for (int i = int(a); i >= int(b); --i) #define rep(i, n) for (int i = 0; i < int(n); ++i) #define mkp(a, b) make_pair(a, b) using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> PII; typedef vector<int> VI; typedef vector<PII> VPI; typedef vector<VI> VVI; typedef vector<VVI> VVVI; typedef vector<VPI> VVPI; typedef pair<ll, ll> PLL; typedef vector<ll> VL; typedef vector<PLL> VPL; typedef vector<VL> VVL; typedef vector<VVL> VVVL; typedef vector<VPL> VVPL; template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;} template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;} #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; template<class T> using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef vector<char> VC; typedef vector<VC> VVC; typedef vector<bool> VB; typedef vector<VB> VVB; int n, m; int K, L; void replace(VVC& table, char a, char b) { rep(i, n) rep(j, m) if (table[i][j] == a) table[i][j] = b; } const int MAXN = 300; bool aexist[MAXN][MAXN]; bool bexist[MAXN][MAXN]; VPI harevan(int x, int y) { VPI ret; ret.pb({x-1, y}); ret.pb({x+1, y}); ret.pb({x, y-1}); ret.pb({x, y+1}); VPI ret2; for (auto[x, y] : ret) { if (x < 0 || x >= n) continue; if (y < 0 || y >= m) continue; ret2.pb({x, y}); } return ret2; } void solve() { cin >> m >> n >> K >> L; // K - width, L - height rep(i, n) rep(j, m) aexist[i][j] = bexist[i][j] = 0; int hx, hy, vx, vy; cin >> hy >> hx >> vy >> vx; VVC table, a, b; table = a = b = VVC(n, VC(m, 'X')); rep(i, n) rep(j, m) cin >> table[i][j]; int destx, desty; rep(i, n) rep(j, m) { if (table[i][j] == '*') { destx = i; desty = j; table[i][j] = '.'; break; } } rep(i, n) rep(j, m) { if (j+K-1 < m) { bool can = true; replr(c, j, j+K-1) { if (table[i][c] == 'X') can = false; } if (can) a[i][j] = '.'; } if (i+L-1 < n) { bool can = true; replr(r, i, i+L-1) { if (table[r][j] == 'X') can = false; } if (can) b[i][j] = '.'; } } /*cout << endl << "possible moves horizontal" << endl;*/ /*rep(i, n) {*/ /* rep(j, m) cout << a[i][j];*/ /* cout << endl;*/ /*}*/ /*cout << endl << "possible moves vertical" << endl;*/ /*rep(i, n) {*/ /* rep(j, m) cout << b[i][j];*/ /* cout << endl;*/ /*}*/ stack<PII> ast; stack<PII> bst; ast.push({hx, hy}); bst.push({vx, vy}); aexist[hx][hy] = true; bexist[vx][vy] = true; while (ast.size() || bst.size()) { while (ast.size()) { auto[ax, ay] = ast.top(); ast.pop(); /*cout << "PROCESSING HORIZONTAL AT (" << ax << ", " << ay << ")" << endl;*/ int MINX = max(0, ax-L+1); int MAXX = ax; int MINY = ay; int MAXY = ay+K-1; while (true) { bool repeat = false; replr(x, MINX, MAXX) { replr(y, MINY, MAXY) { if (b[x][y] != 'X' && !bexist[x][y]) { bool canbe = false; for (auto[vx, vy] : harevan(x, y)) { if (MINX <= vx && vx <= MAXX && MINY <= vy && vy <= MAXY) { if (bexist[vx][vy]) canbe = true; } } if (canbe) { /*cout << " IT TURNS OUT THAT VERTICAL CAN BE AT (" << x << ", " << y << ")" << endl;*/ bst.push({x, y}); bexist[x][y] = true; repeat = true; } } } } if (!repeat) break; } } while (bst.size()) { auto[bx, by] = bst.top(); bst.pop(); /*cout << "PROCESSING VERTICAL AT (" << bx << ", " << by << ")" << endl;*/ int MINX = bx; int MAXX = min(n-1, bx+L-1); int MINY = max(by-K+1, 0); int MAXY = by; while (true) { bool repeat = false; replr(x, MINX, MAXX) { replr(y, MINY, MAXY) { if (a[x][y] != 'X' && !aexist[x][y]) { bool canbe = false; for (auto[vx, vy] : harevan(x, y)) { if (MINX <= vx && vx <= MAXX && MINY <= vy && vy <= MAXY) { if (aexist[vx][vy]) canbe = true; } } if (canbe) { /*cout << " IT TURNS OUT THAT HORIZONTAL CAN BE AT (" << x << ", " << y << ")" << endl;*/ ast.push({x, y}); aexist[x][y] = true; repeat = true; } } } } if (!repeat) break; } } } /*cout << "Horizontal can be in " << endl;*/ /*rep(x, n) rep(y, m) if (aexist[x][y]) {*/ /* cout << "(" << x << ", " << y << ")" << endl;*/ /*}*/ /*cout << "Vertical can be in " << endl;*/ /*rep(x, n) rep(y, m) if (bexist[x][y]) {*/ /* cout << "(" << x << ", " << y << ")" << endl;*/ /*}*/ bool p1 = false; rep(y, m) if (aexist[destx][y]) { if (desty-K+1 <= y && y <= desty) { p1 = true; break; } } bool p2 = false; rep(x, n) if (bexist[x][desty]) { if (destx-L+1 <= x && x <= destx) { p2 = true; break; } } if (p1 && p2) cout << "YES" << endl; else cout << "NO" << endl; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); /*freopen("mincross.in", "r", stdin); */ /*freopen("test.out", "w", stdout); */ int t = 1; //cin >> t; while (t--) solve(); }

Compilation message (stderr)

Main.cpp: In function 'VPI harevan(int, int)':
Main.cpp:56:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |     for (auto[x, y] : ret) {
      |              ^
Main.cpp: In function 'void solve()':
Main.cpp:116:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  116 |             auto[ax, ay] = ast.top();
      |                 ^
Main.cpp:131:38: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  131 |                             for (auto[vx, vy] : harevan(x, y)) {
      |                                      ^
Main.cpp:149:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  149 |             auto[bx, by] = bst.top();
      |                 ^
Main.cpp:162:38: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  162 |                             for (auto[vx, vy] : harevan(x, y)) {
      |                                      ^
Main.cpp:73:9: warning: 'destx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   73 |     int destx, desty;
      |         ^~~~~
Main.cpp:73:16: warning: 'desty' may be used uninitialized in this function [-Wmaybe-uninitialized]
   73 |     int destx, desty;
      |                ^~~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...