oj.uz

Submission #1087346

# Submission time Handle Problem Language Result Execution time Memory
1087346 2024-09-12T14:05:24 Z anhthi Furniture (JOI20_furniture) C++14
100 / 100
 206 ms 16984 KB 
#include <bits/stdc++.h>

using namespace std;


#define fi first
#define se second
#define ll long long
#define mp(x, y) make_pair(x, y)
#define sz(v) ((int) (v).size())
#define all(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define BIT(x, y) (((x) >> (y)) & 1)
#define pb push_back
#define max_rng *max_element
#define min_rng *min_element
#define rep(i, n) for(int i = 1, _n = (n); i <= _n; ++i)
#define forn(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i)
#define ford(i, a, b) for(int i = (a), _b = (b); i >= _b; --i)

template <class X, class Y>
    inline bool maximize(X &x, Y y) {
        return (x < y ? x = y, true : false);
    }

template <class X, class Y>
    inline bool minimize(X &x, Y y) {
        return (x > y ? x = y, true : false);
    }

template <class X>
    inline void compress(vector<X> &a) {
        sort(all(a));
        a.resize(unique(all(a)) - a.begin());
    }

int ctz(ll x) { return __builtin_ctzll(x); }
int lg(ll x) { return 63 - __builtin_clzll(x); }
int popcount(ll x) { return __builtin_popcount(x); }

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) {
    return l + abs((ll) rng()) % (r - l + 1);
}

const ll oo = (ll) 1e17;
const int inf = (ll) 2e9 + 7, mod = (ll) 1e9 + 7;

const int mxn = 1e3 + 5;
const int LG = 18, BASE = 311;

void add(int &x, int y) { x += y; if (x >= mod) x -= mod; }
void sub(int &x, int y) { x -= y; if (x < 0) x += mod; }

int n, m, q;
int a[mxn][mxn];

bool ok[mxn][mxn];
int sum[mxn << 1 + 5];

int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};

void backtrack(int i, int j) {
    if (ok[i][j]) return;

    sum[i+j]--;
    ok[i][j] = true;

    if (ok[i+1][j-1]) {
        backtrack(i+1, j);
        backtrack(i, j-1);
    }
    if (ok[i-1][j+1]) {
        backtrack(i, j+1);
        backtrack(i-1, j);
    }

    return;
}

int main(void) {

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    #define TASK "task"
    if (fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }

    cin >> n >> m;
    rep(i, n) rep(j, m) cin >> a[i][j];

    rep(i, n) ok[i][0] = ok[i][m+1] = 1;
    rep(i, m) ok[0][i] = ok[n+1][i] = 1;

    rep(i, n) rep(j, m) sum[i + j]++;
    rep(i, n) rep(j, m) if (a[i][j]) {
        backtrack(i, j);
    }
    cin >> q;
    rep(_, q) {

        int x, y;
        cin >> x >> y;

        if (ok[x][y]) {
            cout << 1 << '\n';
        }
        else {
            if (sum[x + y] > 1) {
                cout << 1 << '\n';
                backtrack(x, y);
            }
            else {
                cout << 0 << '\n';
            }
        }
    }

    return 0;
}

Compilation message

furniture.cpp:59:18: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   59 | int sum[mxn << 1 + 5];
      |                ~~^~~
furniture.cpp: In function 'int main()':
furniture.cpp:89:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
furniture.cpp:90:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 2 ms 1060 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 2 ms 1116 KB Output is correct
9 Correct 2 ms 860 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 2 ms 1060 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 2 ms 1116 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 6 ms 1116 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 82 ms 9812 KB Output is correct
13 Correct 37 ms 6856 KB Output is correct
14 Correct 154 ms 14628 KB Output is correct
15 Correct 151 ms 14792 KB Output is correct
16 Correct 158 ms 15696 KB Output is correct
17 Correct 170 ms 16468 KB Output is correct
18 Correct 167 ms 16208 KB Output is correct
19 Correct 172 ms 16976 KB Output is correct
20 Correct 168 ms 16984 KB Output is correct
21 Correct 206 ms 16976 KB Output is correct