Submission #366841

#	Time	Username	Problem	Language	Result	Execution time	Memory
366841		topovik	Patkice (COCI20_patkice)	C++14	50 / 50	1 ms	492 KiB

patkice

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second

using namespace std;

typedef long long ll;

const ll oo = 1e9;
const ll N = 1e3;

vector <pair<vector <char>, bool> > ans;
bool mrk[N][N];
string s[N];
int n, m;

int sx, sy;

bool good(int x, int y)
{
    return (x >= 0 && y >= 0 && x < n && y < m);
}

void Rec(int x, int y)
{
    if (good(x, y) && mrk[x][y] || s[x][y] == '.' || s[x][y] == 'o')
    {
        ans.back().s = 0;
        return;
    }
    if (s[x][y] == 'x') return;
    mrk[x][y] = 1;
    if (s[x][y] == '^') x--;
    else
    if (s[x][y] == 'v') x++;
    else
    if (s[x][y] == '<') y--;
    else
    if (s[x][y] == '>') y++;
    ans.back().f.pb('v');
    Rec(x, y);
}

void clear()
{
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) mrk[i][j] = 0;
}

void Check()
{
    ans.pb({{}, 1});
    ans.back().f.pb('N');
    clear();
    Rec(sx - 1, sy);
    ans.pb({{}, 1});
    ans.back().f.pb('S');
    clear();
    Rec(sx + 1, sy);
    ans.pb({{}, 1});
    ans.back().f.pb('E');
    clear();
    Rec(sx, sy + 1);
    ans.pb({{}, 1});
    ans.back().f.pb('W');
    clear();
    Rec(sx, sy - 1);
}

bool cmp(pair<vector <char>, bool> _a, pair<vector <char>, bool> _b)
{
    if (!_b.s) return 1;
    if (!_a.s) return 0;
    if (_a.f.size() != _b.f.size()) return _a.f.size() < _b.f.size();
    return _a.f[0] < _b.f[0];
}

int main() {
    ios_base::sync_with_stdio(0);
    iostream::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> s[i];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
        if (s[i][j] == 'o') sx = i, sy = j;
    Check();
    sort(ans.begin(), ans.end(), cmp);
    if (!ans[0].s) cout << ":(" << endl;
    else cout << ":)\n" << ans[0].f[0];
}

Compilation message (stderr)

patkice.cpp: In function 'void Rec(int, int)':
patkice.cpp:27:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   27 |     if (good(x, y) && mrk[x][y] || s[x][y] == '.' || s[x][y] == 'o')
      |         ~~~~~~~~~~~^~~~~~~~~~~~

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