oj.uz

Submission #649409

# Submission time Handle Problem Language Result Execution time Memory
649409 2022-10-10T07:37:54 Z BackNoob Furniture (JOI20_furniture) C++14
100 / 100
 313 ms 15948 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1)
#define TASK "task"
#define sz(s) (int) (s).size()

using namespace std;
const int mxN = 5e5 + 227;
const int inf = 1e9 + 277;
const int mod = 1e9 + 7;
const ll infll = 1e18 + 7;
const int base = 307;
const int LOG = 20;

template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}

int n;
int m;
int numq;
int a[1007][1007];
int f[mxN];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
queue<pair<int, int>> q;

bool ok(int x, int y)
{
    return (1 <= x && x <= n && 1 <= y && y <= m);
}

bool add(int x, int y)
{
    if(a[x][y] == 1) return 1;
    if(f[x + y] == 1) return 0;

    a[x][y] = 1;
    f[x + y]--;
    q.push({x, y});

    while(!q.empty()) {
        int x = q.front().fi;
        int y = q.front().se;
        q.pop();

        if(a[x - 1][y + 1] == 1) {

            if(ok(x - 1, y) == true && a[x - 1][y] == 0) {
                a[x - 1][y] = 1;
                f[x - 1 + y]--;
                q.push({x - 1, y});
            }
            if(ok(x, y + 1) == true && a[x][y + 1] == 0) {
                a[x][y + 1] = 1;
                f[x + y + 1]--;
                q.push({x, y + 1});
            }

        }
        if(a[x + 1][y - 1] == 1) {
            if(ok(x, y - 1) == true && a[x][y - 1] == 0) {
                a[x][y - 1] = 1;
                f[x + y - 1]--;
                q.push({x, y - 1});
            }
            if(ok(x + 1, y) == true && a[x + 1][y] == 0) {
                a[x + 1][y] = 1;
                f[x + 1 + y]--;
                q.push({x + 1, y});
            }
        }
    }
    return true;
}

void solve()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++) f[i + j]++;

    for(int i = 0; i <= n + 1; i++)
    for(int j = 0; j <= m + 1; j++) {
        if(1 <= i && i <= n && 1 <= j && j <= m) continue;
        a[i][j] = 1;
    }

    for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++) {
        int x;
        cin >> x;
        if(x == 1) add(i, j);
    }

    cin >> numq;
    while(numq--) {
        int x, y;
        cin >> x >> y;
        cout << add(x, y) << endl;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen(TASK".inp" , "r" , stdin);
    //freopen(TASK".out" , "w" , stdout);

    int tc = 1;
    //cin >> tc;
    while(tc--) {
    	solve();
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 3 ms 724 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 3 ms 724 KB Output is correct
8 Correct 4 ms 724 KB Output is correct
9 Correct 4 ms 724 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 3 ms 724 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 3 ms 724 KB Output is correct
8 Correct 4 ms 724 KB Output is correct
9 Correct 4 ms 724 KB Output is correct
10 Correct 10 ms 852 KB Output is correct
11 Correct 3 ms 592 KB Output is correct
12 Correct 136 ms 8716 KB Output is correct
13 Correct 55 ms 5888 KB Output is correct
14 Correct 252 ms 13380 KB Output is correct
15 Correct 282 ms 13728 KB Output is correct
16 Correct 240 ms 14692 KB Output is correct
17 Correct 293 ms 15436 KB Output is correct
18 Correct 258 ms 15028 KB Output is correct
19 Correct 313 ms 15912 KB Output is correct
20 Correct 267 ms 15948 KB Output is correct
21 Correct 279 ms 15728 KB Output is correct