oj.uz

Submission #571019

# Submission time Handle Problem Language Result Execution time Memory
571019 2022-06-01T04:45:43 Z f4t4nt Mecho (IOI09_mecho) C++11
4 / 100
 1 ms 212 KB 
#include <algorithm>
#include <cmath>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <iomanip>
#include <iterator>
#include <list>
#include <map>
#include <math.h>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string>
#include <tuple>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using ch = char;
using str = string;

#define pb push_back
#define elif else if
#define sz(C) (ll) C.size()
#define mp make_pair
#define mt make_tuple
#define flip(C) reverse(C.begin(), C.end())
#define ssort(C) sort(C.begin(), C.end())
#define rsort(C) sort(C.begin(), C.end(), greater<>())

#define FOR(x, e) for(ll  x = 0; x < (ll) e; x++)
#define FORR(x, e) for(ll x = (ll) e - 1; x >= 0; x--)
#define FOB(x, b, e) for(auto x = b; x < e; x++)
#define FOI(x, e, i) for(ll x = 0; x < (ll) e; x += (ll) i)
#define FOBI(x, b, e, i) for(ll x = (ll) b; x < (ll) e; x += (ll) i)
#define FORE(x, C) for(auto &x : C)

#ifdef LOCAL
#include "tester.cpp"
#define main test_main
extern istringstream fin;
extern ostringstream fout;
string test_file_name = "tests";
#define cin fin
#define cout fout
#endif

vector<int> di { -1, 0, 1, 0};
vector<int> dj { 0, -1, 0, 1};

void fill_b(ll &n, vector<vector<char>> &g, queue<pair<ll, ll>> &bfs_b, vector<vector<ll>> &d_b) {
    while(sz(bfs_b)) {
        ll i0 = bfs_b.front().first, j0 = bfs_b.front().second;
        bfs_b.pop();
        FOR(k, 4) {
            ll i1 = i0 + di[k], j1 = j0 + dj[k];
            if(i1 < 0 || i1 >= n || j1 < 0 || j1 >= n) continue;
            if(g[i1][j1] == 'T' || g[i1][j1] == 'D') continue;
            if(d_b[i1][j1] != 1e18) continue;
            d_b[i1][j1] = d_b[i0][j0] + 1;
            bfs_b.push({i1, j1});
        }
    }
}

bool valid(ll &mid, ll &n, ll &s, vector<vector<ll>> &d_b, vector<vector<char>> &g, queue<pair<ll, ll>> bfs_m, vector<vector<ll>> d_m) {
    while(sz(bfs_m)) {
        ll i0 = bfs_m.front().first, j0 = bfs_m.front().second, d = d_m[i0][j0] + 1;
        bfs_m.pop();
        FOR(k, 4) {
            ll i1 = i0 + di[k], j1 = j0 + dj[k];
            if(i1 < 0 || i1 >= n || j1 < 0 || j1 >= n) continue;
            if(g[i1][j1] == 'T') continue;
            if(d_m[i1][j1] != 1e18) continue;
            if(d_b[i1][j1] < mid + d / s) continue;
            if(g[i1][j1] == 'D') return true;
            d_m[i1][j1] = d;
            bfs_m.push({i1, j1});
        }
    }
    return false;
}

int main() {
    cout << "-1\n";
    return 0;
    ll n, s, lo = 0, hi = 1e18;
    cin >> n >> s;
    vector<vector<char>> g(n, vector<char>(n));
    vector<vector<ll>> d_b(n, vector<ll>(n, 1e18)), d_m(n, vector<ll>(n, 1e18));
    queue<pair<ll, ll>> bfs_b, bfs_m;
    FOR(i, n) FOR(j, n) {
        cin >> g[i][j];
        if(g[i][j] == 'H') {
            bfs_b.push({i, j});
            d_b[i][j] = 0;
        }
        elif(g[i][j] == 'M') {
            bfs_m.push({i, j});
            d_m[i][j] = 0;
        }
    }
    fill_b(n, g, bfs_b, d_b);
    while(hi - lo > 0) {
        ll mid = lo + (hi - lo + 1) / 2;
        if(valid(mid, n, s, d_b, g, bfs_m, d_m)) lo = mid;
        else hi = mid - 1;
    }
    lo--;
    if(valid(lo, n, s, d_b, g, bfs_m, d_m)) cout << lo << '\n';
    else cout << "-1\n";
    return 0;
}

Subtask #1
4.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Incorrect 0 ms 212 KB Output isn't correct
8 Correct 0 ms 212 KB Output is correct
9 Incorrect 1 ms 212 KB Output isn't correct
10 Incorrect 1 ms 212 KB Output isn't correct
11 Incorrect 1 ms 212 KB Output isn't correct
12 Incorrect 1 ms 212 KB Output isn't correct
13 Incorrect 1 ms 212 KB Output isn't correct
14 Correct 1 ms 212 KB Output is correct
15 Incorrect 1 ms 212 KB Output isn't correct
16 Incorrect 1 ms 212 KB Output isn't correct
17 Incorrect 1 ms 212 KB Output isn't correct
18 Incorrect 1 ms 212 KB Output isn't correct
19 Incorrect 0 ms 212 KB Output isn't correct
20 Incorrect 0 ms 212 KB Output isn't correct
21 Incorrect 0 ms 212 KB Output isn't correct
22 Incorrect 1 ms 212 KB Output isn't correct
23 Incorrect 1 ms 212 KB Output isn't correct
24 Incorrect 1 ms 212 KB Output isn't correct
25 Incorrect 1 ms 212 KB Output isn't correct
26 Incorrect 1 ms 212 KB Output isn't correct
27 Incorrect 1 ms 212 KB Output isn't correct
28 Incorrect 1 ms 212 KB Output isn't correct
29 Incorrect 0 ms 212 KB Output isn't correct
30 Incorrect 0 ms 212 KB Output isn't correct
31 Incorrect 1 ms 212 KB Output isn't correct
32 Incorrect 1 ms 212 KB Output isn't correct
33 Incorrect 0 ms 212 KB Output isn't correct
34 Incorrect 1 ms 212 KB Output isn't correct
35 Incorrect 1 ms 212 KB Output isn't correct
36 Incorrect 0 ms 212 KB Output isn't correct
37 Incorrect 1 ms 212 KB Output isn't correct
38 Incorrect 1 ms 212 KB Output isn't correct
39 Incorrect 0 ms 212 KB Output isn't correct
40 Incorrect 1 ms 212 KB Output isn't correct
41 Incorrect 1 ms 212 KB Output isn't correct
42 Incorrect 1 ms 212 KB Output isn't correct
43 Incorrect 0 ms 212 KB Output isn't correct
44 Incorrect 1 ms 212 KB Output isn't correct
45 Incorrect 1 ms 212 KB Output isn't correct
46 Incorrect 0 ms 212 KB Output isn't correct
47 Incorrect 1 ms 212 KB Output isn't correct
48 Incorrect 0 ms 212 KB Output isn't correct
49 Incorrect 1 ms 212 KB Output isn't correct
50 Incorrect 0 ms 212 KB Output isn't correct
51 Incorrect 0 ms 212 KB Output isn't correct
52 Incorrect 0 ms 212 KB Output isn't correct
53 Incorrect 1 ms 212 KB Output isn't correct
54 Incorrect 0 ms 212 KB Output isn't correct
55 Incorrect 0 ms 212 KB Output isn't correct
56 Incorrect 0 ms 212 KB Output isn't correct
57 Incorrect 1 ms 212 KB Output isn't correct
58 Incorrect 0 ms 212 KB Output isn't correct
59 Incorrect 1 ms 212 KB Output isn't correct
60 Incorrect 0 ms 212 KB Output isn't correct
61 Incorrect 0 ms 212 KB Output isn't correct
62 Incorrect 1 ms 212 KB Output isn't correct
63 Incorrect 1 ms 212 KB Output isn't correct
64 Incorrect 0 ms 212 KB Output isn't correct
65 Incorrect 1 ms 212 KB Output isn't correct
66 Incorrect 0 ms 212 KB Output isn't correct
67 Correct 1 ms 212 KB Output is correct
68 Incorrect 1 ms 212 KB Output isn't correct
69 Incorrect 1 ms 212 KB Output isn't correct
70 Incorrect 0 ms 212 KB Output isn't correct
71 Incorrect 1 ms 212 KB Output isn't correct
72 Incorrect 0 ms 212 KB Output isn't correct
73 Incorrect 0 ms 212 KB Output isn't correct
74 Incorrect 0 ms 212 KB Output isn't correct
75 Incorrect 1 ms 212 KB Output isn't correct
76 Incorrect 1 ms 212 KB Output isn't correct
77 Incorrect 0 ms 212 KB Output isn't correct
78 Correct 0 ms 212 KB Output is correct
79 Incorrect 1 ms 212 KB Output isn't correct
80 Incorrect 1 ms 212 KB Output isn't correct
81 Incorrect 1 ms 212 KB Output isn't correct
82 Incorrect 0 ms 212 KB Output isn't correct
83 Incorrect 0 ms 212 KB Output isn't correct
84 Incorrect 1 ms 212 KB Output isn't correct
85 Incorrect 0 ms 212 KB Output isn't correct
86 Incorrect 0 ms 212 KB Output isn't correct
87 Incorrect 0 ms 212 KB Output isn't correct
88 Incorrect 0 ms 212 KB Output isn't correct
89 Incorrect 1 ms 212 KB Output isn't correct
90 Incorrect 0 ms 212 KB Output isn't correct
91 Incorrect 1 ms 212 KB Output isn't correct
92 Incorrect 0 ms 212 KB Output isn't correct