Submission #294604

#TimeUsernameProblemLanguageResultExecution timeMemory
294604DenisovFurniture (JOI20_furniture)C++14
0 / 100
2 ms384 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() { ios::sync_with_stdio(0); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m, x; cin >> n >> m; 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 || 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 (x == n - 1 && y == m - 1) return true; if (go(x, y + 1)) { return true; } if (go(x + 1, y)) { f[x] = m - y - 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]) { if (x == n - 1) return false; a[x][y] = 1; vector <int> F = f; f[x] = m - y; int X = x; while (X > 0 && f[X] > f[X - 1]) { f[X - 1] = f[X]; --X; } ++cnt; int Y = y - 1; while (true) { if (Y < 0) { f = F; a[x][y] = 0; return false; } if (go(X, Y)) { return true; } --Y; } } // cout << "in\n"; a[x][y] = 1; return true; }; auto print_f = [&] () { for (auto &i : f) { cout << i << ' '; } cout << '\n'; }; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> x; if (x) { assert(upd(i, j)); } } } // print_f(); int q, y; cin >> q; while (q--) { cin >> x >> y; --x, --y; cout << upd (x, y) << '\n'; // print_f(); } }

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:110:10: warning: variable 'print_f' set but not used [-Wunused-but-set-variable]
  110 |     auto print_f = [&] () {
      |          ^~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...