제출 #318136

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
318136		greengrass19000	Patkice (COCI20_patkice)	C++14	0 / 50	1 ms	364 KiB

patkice

/**Bogosort**/
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define maxn 405
#define maxm 1000006
#define maxc 1000000007
#define pii pair <int,int>
#define ii pair <int,int>
#define Task ""
//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")
template <typename T> inline void read(T &x){char c;bool nega=0;while((!isdigit(c=getchar()))&&(c!='-'));if(c=='-'){nega=1;c=getchar();}x=c-48;while(isdigit(c=getchar())) x=x*10+c-48;if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10);putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){putchar('-');x=-x;}writep(x);putchar(' ');}
template <typename T> inline void writeln(T x){write(x);putchar('\n');}
using namespace std;
int n, m, d[10005];
char c[10005];
ii start;
int End;
inline int cv(int x, int y) {
	return (x - 1) * m + y;
}
ii cv2(int x) {
	return make_pair((x - 1) / m + 1, (x - 1) % m + 1);
}
inline bool valid(int x, int y) {
	return (x && y && x <= n && y <= m && c[cv(x, y)] != '.');
}
void dfs(int u) {
	if(u == cv(start.F, start.S)) return;
	int x = cv2(u).F;
	int y = cv2(u).S;
	if(c[u] == '>') {
		++y;
	}
	if(c[u] == '<') {
		--y;
	}
	if(c[u] == 'v') {
		++x;
	}
	if(c[u] == '^') {
		--x;
	}
	if(!valid(x, y)) return;
	if(d[cv(x, y)] > d[u]) {
		d[cv(x, y)] = d[u];
		dfs(cv(x, y));
	}
}
int main() {
    //srand(time(NULL));
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie();
//    if(fopen(".inp", "r")) freopen(".inp", "r", stdin);
	cin >> n >> m;
	fo(i, 1, n) fo(j, 1, m) {
		cin >> c[cv(i, j)];
		if(c[cv(i, j)] == 'o') {
			start = {i, j};
		}
		if(c[cv(i, j)] == 'x') {
			End = cv(i, j);
		}
	}
	int ans = 2e9;
	int dir = 0;
	int xs, ys;
	xs = start.F;
	ys = start.S + 1;
	fo(i, 1, n) fo(j, 1, m) d[cv(i, j)] = 2e9;
	if(xs && ys && xs <= n && ys <= m && c[cv(xs, ys)] != '.') {
		d[cv(xs, ys)] = 1;
		dfs(cv(xs, ys));
	}
	if(d[End] < ans && d[End]) {
		ans = End;
		dir = 0;
	}
	xs = start.F + 1;
	ys = start.S;
	fo(i, 1, n) fo(j, 1, m) d[cv(i, j)] = 2e9;
	if(xs && ys && xs <= n && ys <= m && c[cv(xs, ys)] != '.') {
		d[cv(xs, ys)] = 1;
		dfs(cv(xs, ys));
	}
	if(d[End] < ans && d[End]) {
		ans = End;
		dir = 1;
	}
	xs = start.F - 1;
	ys = start.S;
	fo(i, 1, n) fo(j, 1, m) d[cv(i, j)] = 2e9;
	if(xs && ys && xs <= n && ys <= m && c[cv(xs, ys)] != '.') {
		d[cv(xs, ys)] = 1;
		dfs(cv(xs, ys));
	}
	if(d[End] < ans && d[End]) {
		ans = End;
		dir = 2;
	}
	xs = start.F;
	ys = start.S - 1;
	fo(i, 1, n) fo(j, 1, m) d[cv(i, j)] = 2e9;
	if(xs && ys && xs <= n && ys <= m && c[cv(xs, ys)] != '.') {
		d[cv(xs, ys)] = 1;
		dfs(cv(xs, ys));
	}
	if(d[End] < ans && d[End]) {
		ans = End;
		dir = 3;
	}
	if(ans == 2e9) {
		cout << ":(";
		return 0;
	}
	cout << ":)\n";
	string s = "ENSW"; cout << s[dir];
	return 0;
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 20