oj.uz

Submission #1019722

# Submission time Handle Problem Language Result Execution time Memory
1019722 2024-07-11T08:17:13 Z cpptowin Furniture (JOI20_furniture) C++17
100 / 100
 235 ms 23332 KB 
#include <bits/stdc++.h>
#define fo(i, d, c) for (int i = d; i <= c; i++)
#define fod(i, c, d) for (int i = c; i >= d; i--)
#define maxn 1000010
#define N 5010
#define fi first
#define se second
#define pb emplace_back
#define en cout << "\n";
#define int long long
#define inf (int)1e18
#define bitcount(x) __builtin_popcountll(x)
#define pii pair<int, int>
#define vii vector<pii>
#define lb(x) x & -x
#define bit(i, j) ((i >> j) & 1)
#define offbit(i, j) (i ^ (1LL << j))
#define onbit(i, j) (i | (1LL << j))
#define vi vector<int>
#define all(x) x.begin(), x.end()
#define ss(x) (int)x.size()
using namespace std;
int n,m,q;
int r[N][N],cnt[maxn];
main()
{
#define name "TASK"
    if(fopen(name".inp","r"))
    {
        freopen(name".inp","r",stdin);
        freopen(name".out","w",stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    fo(i,0,n + 1) fo(j,0,m + 1) r[i][j] = 1;
    fo(i,1,n) fo(j,1,m) r[i][j] = 0,cnt[i + j]++;
    const auto solve = [&](const int X, const int Y) -> int
    {
        if (r[X][Y] == 1)
        {
            return 1;
        }
        if (cnt[X + Y] == 1)
        {
            return 0;
        }
        std::stack<std::pair<int, int>> st;
        const auto push = [&](const int x, const int y)
        {
            if (r[x][y] == 0)
            {
                r[x][y] = 1;
                --cnt[x + y];
                st.emplace(x, y);
            }
        };
        push(X, Y);
        while (!st.empty())
        {
            const int x = st.top().first;
            const int y = st.top().second;
            st.pop();
            if (r[x - 1][y + 1] == 1)
            {
                push(x - 1, y);
                push(x, y + 1);
            }
            if (r[x + 1][y - 1] == 1)
            {
                push(x, y - 1);
                push(x + 1, y);
            }
        }
        return 1;
    };
    fo(i,1,n) fo(j,1,m)
    {
        int x;
        cin >> x;
        if(x == 1) solve(i,j);
    }
    cin >> q;
    while(q--)
    {
        int i,j;
        cin >> i >> j;
        cout << solve(i,j);
        en;
    }
}

Compilation message

furniture.cpp:25:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   25 | main()
      | ^~~~
furniture.cpp: In function 'int main()':
furniture.cpp:30:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |         freopen(name".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
furniture.cpp:31:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         freopen(name".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 956 KB Output is correct
3 Correct 2 ms 856 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 860 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 2 ms 860 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 600 KB Output is correct
2 Correct 1 ms 956 KB Output is correct
3 Correct 2 ms 856 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 860 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 6 ms 1372 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 95 ms 16312 KB Output is correct
13 Correct 71 ms 12992 KB Output is correct
14 Correct 172 ms 20048 KB Output is correct
15 Correct 218 ms 19796 KB Output is correct
16 Correct 209 ms 21328 KB Output is correct
17 Correct 177 ms 22612 KB Output is correct
18 Correct 222 ms 21976 KB Output is correct
19 Correct 235 ms 23276 KB Output is correct
20 Correct 196 ms 23332 KB Output is correct
21 Correct 197 ms 23276 KB Output is correct