| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1045766 |
2024-08-06T07:31:11 Z |
VahanAbraham |
Toy (CEOI24_toy) |
C++17 |
|
59 ms |
5244 KB |
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <list>
#include <unordered_set>
#include <unordered_map>
#include <math.h>
#include <bitset>
#include <cmath>
#include <vector>
#include <iomanip>
#include <random>
#include <chrono>
#include <cassert>
using namespace std;
#define ll long long
#define fr first
#define sc second
#define pb push_back
#define US freopen(".in", "r", stdin); freopen("j.out", "w", stdout);
ll gcd(ll a, ll b)
{
if (a == 0 || b == 0) {
return max(a, b);
}
if (a <= b) {
return gcd(a, b % a);
}
else {
return gcd(a % b, b);
}
}
ll lcm(ll a, ll b) {
return (a / gcd(a, b)) * b;
}
const int N = 30;
const ll oo = 100000000000000000, MOD = 1000000007;
struct cord {
int x, y;
};
char grid[N][N];
bool normalahor[N][N], normalaver[N][N];
int w, h, k, l, xend, yend;
map <pair<int, pair<int, pair<int, int>>>, bool> ok;
int dxhor[3] = { 1,-1,0 };
int dxver[3] = { 1,-1,0 };
int dyhor[3] = { 1,-1,0 };
int dyver[3] = { 1,-1,0 };
queue<pair<cord, cord>> q;
pair<int, int> hatvumen(cord hor, cord ver) {
for (int i = ver.x; i <= ver.x; ++i) {
if (hor.y >= ver.y && hor.y <= ver.y + l - 1 && i >=hor.x && i<=hor.x+k-1) {
return { i,hor.y };
}
}
return{ -1,-1 };
}
bool mejnahor(cord hor) {
if (hor.x >= 0 && hor.x + k - 1 <= w - 1 && hor.y >= 0 && hor.y <= h - 1) {
return true;
}
return false;
}
bool mejnaver(cord ver) {
if (ver.x >= 0 && ver.x <= w - 1 && ver.y >= 0 && ver.y+l-1 <= h - 1) {
return true;
}
return false;
}
bool normalhor(cord hor) {
for (int i = hor.x; i <= hor.x + k - 1; ++i) {
if (grid[hor.y][i] == 'X') {
return false;
}
}
return true;
}
bool normalver(cord ver) {
for (int i = ver.y; i <= ver.y + l - 1; ++i) {
if (grid[i][ver.x] == 'X') {
return false;
}
}
return true;
}
bool stug(cord hor1, cord ver1) {
if (mejnahor(hor1) == 1 && mejnaver(ver1) == 1 && normalahor[hor1.x][hor1.y] == 1 && normalaver[ver1.x][ver1.y] == 1) {
pair<int, int> p = hatvumen(hor1, ver1);
if (p.fr == xend && p.sc == yend){
return true;
}
else {
if (p.fr != -1) {
if (ok[{hor1.x, { hor1.y,{ver1.x,ver1.y} }}] != 1) {
ok[{hor1.x, { hor1.y,{ver1.x,ver1.y} }}] = 1;
q.push({ hor1,ver1 });
return false;
}
return false;
}
return false;
}
return false;
}
return false;
}
void solve() {
cin >> w >> h >> k >> l;
int xh, yh, xv, yv;
cin >> xh >> yh >> xv >> yv;
cord hor, ver;
hor.x = xh;
hor.y = yh;
ver.x = xv;
ver.y = yv;
ok[{hor.x, { hor.y,{ver.x,ver.y} }}] = 1;
q.push({ hor,ver });
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
cin >> grid[i][j];
if (grid[i][j] == '*') {
xend = j, yend = i;
}
}
}
/*cout << xend << " " << yend << endl;
cord vv;
vv.x = 1, vv.y = 0;
cout << normalver(vv) << endl;*/
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
cord yy;
yy.x = j, yy.y = i;
if (mejnaver(yy)) {
normalaver[j][i] = normalver(yy);
}
if (mejnahor(yy)) {
normalahor[j][i] = normalhor(yy);
}
}
}
while (q.empty() != 1) {
hor = q.front().fr;
ver = q.front().sc;
//cout << hor.x << " " << hor.y << " " << ver.x << " " << ver.y << endl;
q.pop();
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
cord hor1 = hor, ver1 = ver;
hor1.x += dxhor[i];
ver1.x += dxver[j];
if (stug(hor1, ver1)) {
//cout << hor1.x << " " << hor1.y << " " << ver1.x << " " << ver1.y << endl;
cout << "YES" << endl;
return;
}
}
for (int j = 0; j < 3; ++j) {
cord hor1 = hor, ver1 = ver;
hor1.x += dxhor[i];
ver1.y += dyver[j];
if (stug(hor1, ver1)) {
//cout << hor1.x << " " << hor1.y << " " << ver1.x << " " << ver1.y << endl;
cout << "YES" << endl;
return;
}
}
}
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
cord hor1 = hor, ver1 = ver;
hor1.y += dyhor[i];
ver1.x += dxver[j];
if (stug(hor1, ver1)) {
//cout << hor1.x << " " << hor1.y << " " << ver1.x << " " << ver1.y << endl;
cout << "YES" << endl;
return;
}
}
for (int j = 0; j < 3; ++j) {
cord hor1 = hor, ver1 = ver;
hor1.y += dyhor[i];
ver1.y += dyver[j];
if (stug(hor1, ver1)) {
//cout << hor1.x << " " << hor1.y << " " << ver1.x << " " << ver1.y << endl;
cout << "YES" << endl;
return;
}
}
}
}
cout << "NO" << endl;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
//US
int tt = 1;
//cin >> tt;
while (tt--) {
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Runtime error |
59 ms |
5092 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Runtime error |
59 ms |
5092 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Runtime error |
59 ms |
5244 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Runtime error |
59 ms |
5092 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Runtime error |
59 ms |
5092 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
