| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 654993 |
2022-11-02T10:59:24 Z |
nifeshe |
Portal (COCI17_portal) |
C++14 |
|
1000 ms |
125736 KB |
#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
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;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
14 ms |
2964 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
2004 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
81 ms |
9120 KB |
Output is correct |
| 2 |
Correct |
10 ms |
1920 KB |
Output is correct |
| 3 |
Correct |
6 ms |
852 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1103 ms |
125736 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1090 ms |
88660 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1088 ms |
108728 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1103 ms |
117976 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1096 ms |
118388 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
