oj.uz

답안 #294650

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
294650 2020-09-09T07:56:03 Z Denisov Furniture (JOI20_furniture) C++14
100 / 100
 469 ms 20032 KB 
#include <bits/stdc++.h>
#include <ext/rope>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#define int long long
#define pb push_back
#define x first
#define y second
#define mk(a,b) make_pair(a,b)
#define rr return 0
#define sqr(a) ((a)*(a))
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()

using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

template<class value, class cmp = less<value> >
using ordered_set = tree<value, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
template<class value, class cmp = less_equal<value> >
using ordered_multiset = tree<value, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
template<class key, class value, class cmp = less<key> >
using ordered_map = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

/// find_by_order()
/// order_of_key()
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int randll(int l = INT_MIN, int r = INT_MAX) {
    return uniform_int_distribution<int>(l, r)(rng);
}
const int INF = 1e9, MOD = 1e9 + 7; /// think
const ll LINF = 1e18;


const int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
inline bool inside (int x, int y, int n, int m) {
    return 0 <= x && 0 <= y && x < n && y < m;
}

template<class T> bool umin (T &a, T b) {return a > b ? (a = b, true) : false; }
template<class T> bool umax (T &a, T b) {return a < b ? (a = b, true) : false; }


main()
{
//    freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(0);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m, x;
    cin >> n >> m;
//    n = m = 100;
    vector <vector <int> > a(n, vector <int> (m));
    vector <vector <int> > used(n, vector <int> (m));
    vector <int> f(n);
    vector <int> l(m);
    int cnt = 0;
    function<bool(int, int)> go = [&] (int x, int y) {
        if (x == n - 1 && y == m - 1) return true;
        if (x >= n || y >= m) return false;
        if (a[x][y]) return false;
        if (y >= m - f[x]) return false;
        if (used[x][y] == cnt) return false;
        used[x][y] = cnt;
        if (go(x, y + 1)) {
            return true;
        }
        if (go(x + 1, y)) {
            f[x] = m - y - 1;
            return true;
        }
        return false;
    };
    function<bool(int, int)> go1 = [&] (int x, int y) {
        if (x == n - 1 && y == m - 1) return true;
        if (x >= n || y >= m) return false;
        if (a[x][y]) return false;
        if (x >= n - l[y]) return false;
        if (used[x][y] == cnt) return false;
        used[x][y] = cnt;
        if (go1(x + 1, y)) {
            return true;
        }
        if (go1(x, y + 1)) {
            l[y] = n - x - 1;
            return true;
        }
        return false;
    };
    auto upd = [&] (int x, int y) {
        if (m - 1 - (x ? f[x - 1] : m - 1) <= y && y <= m - 1 - f[x] &&
            n - 1 - (y ? l[y - 1] : n - 1) <= x && x <= n - 1 - l[y]) {
                return false;
            }
        if (m - 1 - (x ? f[x - 1] : m - 1) <= y && y <= m - 1 - f[x]) {
            if (x == n - 1) assert(false);
            a[x][y] = 1;
            f[x] = m - y;
            int X = x;
            ++cnt;
            int Y = y - 1;
            while (true) {
                f[X] = m - Y - 1;
                while (X > 0 && f[X] > f[X - 1]) {
                    f[X - 1] = f[X];
                    --X;
                }
                assert(Y >= 0);
                if (go(X, Y)) {
                    return true;
                }
                --Y;
            }
        }
        if (n - 1 - (y ? l[y - 1] : n - 1) <= x && x <= n - 1 - l[y]) {
            a[x][y] = 1;
            ++cnt;
            l[y] = n - x;
            int X = x - 1, Y = y;
            while (true) {
                l[Y] = n - X - 1;
                while (Y > 0 && l[Y] > l[Y - 1]) {
                    l[Y - 1] = l[Y];
                    --Y;
                }
                assert(X >= 0);
                if (go1(X, Y)) {
                    return true;
                }
                --X;
            }
        }
        a[x][y] = 1;
        return true;
    };
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> x;
            if (x) {
                assert(upd(i, j));
            }
        }
    }
    int q, y;
    auto solve = [&] () {
        vector <vector <int> > dp(n, vector <int> (m));
        dp[0][0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (a[i][j]) continue;
                if (i + 1 < n) {
                    umax(dp[i + 1][j], dp[i][j]);
                }
                if (j + 1 < m) {
                    umax(dp[i][j + 1], dp[i][j]);
                }
            }
        }
        return bool(dp[n - 1][m - 1]);
    };
    cin >> q;
//    q = n * m;
    while (q--) {
        cin >> x >> y;
//        x = randll(1, n), y = randll(1, m);
        --x, --y;
//        while (a[x][y] || (x == n - 1 && y == m - 1) || (x == 0 && y == 0)) {
//            x = randll(0, n - 1);
//            y = randll(0, m - 1);
//        }
//        cout << x << ' ' << y << '\n';
//        a[x][y] = 1;
//        int v = solve();
//        a[x][y] = 0;
        int V = upd (x, y);
//        if (V != v) {
//            cout << "bad " << v << ' ' << V << '\n';
//            for (auto &i : f) {
//                cout << i << ' ';
//            }
//            cout << '\n';
//            rr;
//        }
        cout << V << '\n';
    }
}

Compilation message

furniture.cpp:53:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   53 | main()
      |      ^
furniture.cpp: In function 'int main()':
furniture.cpp:155:10: warning: variable 'solve' set but not used [-Wunused-but-set-variable]
  155 |     auto solve = [&] () {
      |          ^~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 404 KB Output is correct
4 Correct 4 ms 512 KB Output is correct
5 Correct 4 ms 512 KB Output is correct
6 Correct 4 ms 512 KB Output is correct
7 Correct 4 ms 512 KB Output is correct
8 Correct 4 ms 512 KB Output is correct
9 Correct 4 ms 512 KB Output is correct

Subtask #2
95.0 / 95.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 404 KB Output is correct
4 Correct 4 ms 512 KB Output is correct
5 Correct 4 ms 512 KB Output is correct
6 Correct 4 ms 512 KB Output is correct
7 Correct 4 ms 512 KB Output is correct
8 Correct 4 ms 512 KB Output is correct
9 Correct 4 ms 512 KB Output is correct
10 Correct 14 ms 1152 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 215 ms 10232 KB Output is correct
13 Correct 81 ms 9080 KB Output is correct
14 Correct 389 ms 11052 KB Output is correct
15 Correct 392 ms 10488 KB Output is correct
16 Correct 380 ms 11256 KB Output is correct
17 Correct 469 ms 19064 KB Output is correct
18 Correct 437 ms 18808 KB Output is correct
19 Correct 401 ms 19960 KB Output is correct
20 Correct 352 ms 20032 KB Output is correct
21 Correct 405 ms 19964 KB Output is correct