Submission #294616

# Submission time Handle Problem Language Result Execution time Memory
294616 2020-09-09T07:15:51 Z Denisov Furniture (JOI20_furniture) C++14
5 / 100
5000 ms 18412 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);
    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;
    };
    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]);
    };
    auto upd = [&] (int x, int y) {
        if (m - 1 - (x ? f[x - 1] : m - 1) <= y && y <= m - 1 - f[x]) {
            if (x == n - 1) return false;
            a[x][y] = 1;
            vector <int> F = f;
            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;
                }
                if (Y < 0) {
                    f = F;
                    a[x][y] = 0;
                    return false;
                }
                if (go(X, Y)) {
                    return true;
                }
                --Y;
            }
        }
        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;
    cin >> q;
    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';
//        cout << upd (x, y) << '\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:83:10: warning: variable 'solve' set but not used [-Wunused-but-set-variable]
   83 |     auto solve = [&] () {
      |          ^~~~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 512 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 5 ms 512 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 14 ms 512 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 512 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 5 ms 512 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 14 ms 512 KB Output is correct
10 Correct 90 ms 1152 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 205 ms 12536 KB Output is correct
13 Correct 74 ms 9208 KB Output is correct
14 Correct 411 ms 17300 KB Output is correct
15 Correct 412 ms 16888 KB Output is correct
16 Correct 409 ms 18412 KB Output is correct
17 Execution timed out 5034 ms 10104 KB Time limit exceeded
18 Halted 0 ms 0 KB -