Submission #654993

#	Time	Username	Problem	Language	Result	Execution time	Memory
654993		nifeshe	Portal (COCI17_portal)	C++14	60 / 120	1103 ms	125736 KiB

portal

#include <bits/stdc++.h>

//#pragma GCC target ("avx2")
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")
//#pragma comment (linker, "/STACK: 268435456")

#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define int long long

using namespace std;

template <typename T> inline bool umin (T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
template <typename T> inline bool umax (T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

ll mod = 998244353;
ll base = 1e6 + 9;
int inf = 3e9;
int MAX = 5e4 + 5;

random_device rd;
mt19937 gen(rd());
uniform_int_distribution<ll> dis(1, inf);

vector<int> pw(8, 1);

struct node {
    int d = 0;
    int x, y;
    int x1 = -1, y1 = -1, x2 = -1, y2 = -1;
    int cnt = 0;
    bool operator < (const node b) const {
        return d < b.d;
    };
    node(int xx, int yy) {
        x = xx;
        y = yy;
    };
    int get() {
        int ans = (x * pw[1] % mod + y * pw[2] % mod + x1 * pw[3] % mod + y1 * pw[4] % mod + x2 * pw[5] % mod + y2 * pw[6] % mod + cnt * pw[7] % mod) % mod;
        return ans;
    };
};
void solve() {
    for(int i = 1; i < 8; i++) {
        pw[i] = (pw[i - 1] * base) % mod;
    }
    int n, m;
    cin >> n >> m;
    vector<vector<char>> a(n, vector<char>(m));
    int sx, sy;
    int ex, ey;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> a[i][j];
            if(a[i][j] == 'C') {
                sx = i;
                sy = j;
            }
            if(a[i][j] == 'F') {
                ex = i;
                ey = j;
            }
        }
    }
    vector<vector<array<pair<int, int>, 4>>> go(n, vector<array<pair<int, int>, 4>>(m));
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(a[i][j] == '#') {
                go[i][j][0] = {i, j};
                continue;
            }
            for(int k = i - 1; k >= 0; k--) {
                if(a[k][j] == '#') {
                    go[i][j][0] = {k + 1, j};
                    break;
                }
            }
        }
    }
    vector<vector<int>> down(n, vector<int>(m));
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(a[i][j] == '#') {
                go[i][j][1] = {i, j};
                continue;
            }
            for(int k = i + 1; k < n; k++) {
                if(a[k][j] == '#') {
                    go[i][j][1] = {k - 1, j};
                    break;
                }
            }
        }
    }
    vector<vector<int>> right(n, vector<int>(m));
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(a[i][j] == '#') {
                go[i][j][2] = {i, j};
                continue;
            }
            for(int k = j - 1; k >= 0; k--) {
                if(a[i][k] == '#') {
                    go[i][j][2] = {i, k + 1};
                    break;
                }
            }
        }
    }
    vector<vector<int>> left(n, vector<int>(m));
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(a[i][j] == '#') {
                go[i][j][3] = {i, j};
                continue;
            }
            for(int k = j + 1; k < m; k++) {
                if(a[i][k] == '#') {
                    go[i][j][3] = {i, k - 1};
                    break;
                }
            }
        }
    }
    vector<int> dx = {1, -1, 0, 0};
    vector<int> dy = {0, 0, 1, -1};
    node start(sx, sy);
    multiset<node> s;
    s.insert(start);
    map<int, int> was;
    while(s.size() > 0) {
        node curr = *s.begin();
        s.erase(s.begin());
        if(was[curr.get()]) {
            continue;
        }
        was[curr.get()] = 1;
        auto [d, x, y, x1, y1, x2, y2, cnt] = curr;
        if(x == ex && y == ey) {
            cout << d << '\n';
            return;
        }
        node tmp = curr;
        for(int i = 0; i < 4 && cnt < 2; i++) {
            tmp = curr;
            if(!~x1) {
                tmp.x1 = go[x][y][i].f;
                tmp.y1 = go[x][y][i].s;
                tmp.cnt = cnt + 1;
                s.insert(tmp);
            }
            else if(!~x2) {
                tmp.x2 = go[x][y][i].f;
                tmp.y2 = go[x][y][i].s;
                tmp.cnt = cnt + 1;
                s.insert(tmp);
            }
            else {
                tmp.x1 = go[x][y][i].f;
                tmp.y1 = go[x][y][i].s;
                tmp.cnt = cnt + 1;
                swap(tmp.x1, tmp.x2);
                swap(tmp.y1, tmp.y2);
                s.insert(tmp);
            }
        }
        tmp = curr;
        if(x == x1 && y == y1 && ~x2) {
            tmp.x = x2;
            tmp.y = y2;
            tmp.d = d + 1;
            tmp.cnt = 0;
            s.insert(tmp);
        }
        tmp = curr;
        if(x == x2 && y == y2 && ~x1) {
            tmp.x = x1;
            tmp.y = y1;
            tmp.d = d + 1;
            tmp.cnt = 0;
            s.insert(tmp);
        }
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(a[nx][ny] == '#') {
                continue;
            }
            node tmp = curr;
            tmp.x = nx;
            tmp.y = ny;
            tmp.d = d + 1;
            tmp.cnt = 0;
            s.insert(tmp);
        }
    }
    cout << "nemoguce\n";
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int ttt = 1;
    //cin >> ttt;
    int ttt0 = ttt;
    while(ttt--) {
        solve();
    }
}

Compilation message (stderr)

portal.cpp: In function 'void solve()':
portal.cpp:146:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  146 |         auto [d, x, y, x1, y1, x2, y2, cnt] = curr;
      |              ^
portal.cpp: In function 'int main()':
portal.cpp:212:9: warning: unused variable 'ttt0' [-Wunused-variable]
  212 |     int ttt0 = ttt;
      |         ^~~~
portal.cpp: In function 'void solve()':
portal.cpp:147:25: warning: 'ey' may be used uninitialized in this function [-Wmaybe-uninitialized]
  147 |         if(x == ex && y == ey) {
      |                       ~~^~~~~
portal.cpp:147:14: warning: 'ex' may be used uninitialized in this function [-Wmaybe-uninitialized]
  147 |         if(x == ex && y == ey) {
      |            ~~^~~~~
portal.cpp:44:11: warning: 'sy' may be used uninitialized in this function [-Wmaybe-uninitialized]
   44 |         y = yy;
      |         ~~^~~~
portal.cpp:58:13: note: 'sy' was declared here
   58 |     int sx, sy;
      |             ^~
portal.cpp:43:11: warning: 'sx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   43 |         x = xx;
      |         ~~^~~~
portal.cpp:58:9: note: 'sx' was declared here
   58 |     int sx, sy;
      |         ^~

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 12 / 12
• Subtask 6: 0 / 12
• Subtask 7: 0 / 12
• Subtask 8: 0 / 12
• Subtask 9: 0 / 12
• Subtask 10: 0 / 12