Submission #294650

#TimeUsernameProblemLanguageResultExecution timeMemory
294650DenisovFurniture (JOI20_furniture)C++14
100 / 100
469 ms20032 KiB
#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 (stderr)

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 = [&] () {
      |          ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...