oj.uz

답안 #715713

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
715713 2023-03-27T15:25:44 Z hamidh100 Furniture (JOI20_furniture) C++17
100 / 100
 3071 ms 13260 KB 
/* In the name of God */

#include <iostream>
#include <iomanip>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <bitset>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <list>
#include <map>
#include <numeric>
#include <limits>
#include <limits.h>
#include <unordered_map>
#include <unordered_set>
#include <chrono>
#include <random>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef map<int, int> MPII;
typedef vector<int> VI;
typedef vector<ll> VL;
#define PB push_back
#define POP pop_back
#define MP make_pair
#define all(a) (a).begin(), (a).end()
#define endl '\n'
#define dbg(x) cerr << '[' << #x << ": " << x << "]\n"
#define dbg2(x, y) cerr << '[' << #x << ": " << x << ", " << #y << ": " << y << "]\n"
#define Yes cout << "Yes\n"
#define YES cout << "YES\n"
#define No cout << "No\n"
#define NO cout << "NO\n"

const ll INF = (ll)2e18 + 1386;
const ld eps = 0.000000000000001;
const int MOD = 1e9 + 7;

inline int mod_(int a){ int res = a + MOD; return (res >= MOD? res - MOD : res); }
inline int mod_add(int a, int b){ int res = a + b; return (res >= MOD? res - MOD : res); }
inline int mod_neg(int a, int b){ int res = (abs(a - b) < MOD? a - b : (a - b) % MOD); return (res < 0? res + MOD : res); }
inline int mod_mlt(int a, int b){ return (1ll * a * b % MOD); }
inline string intToString(ll a){ char x[100]; sprintf(x, "%lld", a); string s = x; return s; }
inline ll stringToInt(string s){ ll res; char x[100]; strcpy(x, s.c_str()); sscanf(x, "%lld", &res); return res; }
inline void fileIO(string i, string o){ freopen(i.c_str(), "r", stdin); freopen(o.c_str(), "w", stdout); }

const int MAXN = 1002;

int n, m, deg1[MAXN][MAXN], degn[MAXN][MAXN];
bool a[MAXN][MAXN], can1[MAXN][MAXN], cann[MAXN][MAXN];

void upd(int x, int y){
    queue<PII> q;
    if (deg1[x][y]){
        deg1[x][y] = 0;
        q.push({x, y});
    }
    while (!q.empty()){
        auto v = q.front();
        int xx = v.first, yy = v.second;
        q.pop();
        can1[xx][yy] = 0;
        deg1[xx + 1][yy]--, deg1[xx][yy + 1]--;
        if (deg1[xx + 1][yy] == 0 && xx + 1 <= n) q.push({xx + 1, yy});
        if (deg1[xx][yy + 1] == 0 && yy + 1 <= m) q.push({xx, yy + 1});
    }

    if (degn[x][y]){
        degn[x][y] = 0;
        q.push({x, y});
    }
    while (!q.empty()){
        auto v = q.front();
        int xx = v.first, yy = v.second;
        q.pop();
        cann[xx][yy] = 0;
        degn[xx - 1][yy]--, degn[xx][yy - 1]--;
        if (degn[xx - 1][yy] == 0 && xx - 1 >= 1) q.push({xx - 1, yy});
        if (degn[xx][yy - 1] == 0 && yy - 1 >= 1) q.push({xx, yy - 1});
    }

}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        fill(can1[i], can1[i] + m + 1, 1);
        fill(cann[i], cann[i] + m + 1, 1);
        fill(deg1[i], deg1[i] + m + 1, 2);
        fill(degn[i], degn[i] + m + 1, 2);
        deg1[i][1] = 1;
        degn[i][m] = 1;
    }
    fill(deg1[1], deg1[1] + m + 1, 1), fill(degn[n], degn[n] + m + 1, 1);

    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin >> a[i][j];
            if (a[i][j] == 1) upd(i, j);
        }
    }
    int q; cin >> q;
    while (q--){
        int x, y;
        cin >> x >> y;
        bool another = 0;
        for (int i = 1; i <= n; i++){
            if (i == x) continue;
            int j = x + y - i;
            if (j < 1 || j > m) continue;
            another |= (can1[i][j] && cann[i][j]);
        }
        cout << another << endl;
        if (another) upd(x, y);
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 2 ms 1364 KB Output is correct
3 Correct 3 ms 1336 KB Output is correct
4 Correct 5 ms 1364 KB Output is correct
5 Correct 6 ms 1364 KB Output is correct
6 Correct 6 ms 1364 KB Output is correct
7 Correct 6 ms 1364 KB Output is correct
8 Correct 6 ms 1364 KB Output is correct
9 Correct 7 ms 1448 KB Output is correct

Subtask #2
95.0 / 95.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 2 ms 1364 KB Output is correct
3 Correct 3 ms 1336 KB Output is correct
4 Correct 5 ms 1364 KB Output is correct
5 Correct 6 ms 1364 KB Output is correct
6 Correct 6 ms 1364 KB Output is correct
7 Correct 6 ms 1364 KB Output is correct
8 Correct 6 ms 1364 KB Output is correct
9 Correct 7 ms 1448 KB Output is correct
10 Correct 17 ms 980 KB Output is correct
11 Correct 4 ms 852 KB Output is correct
12 Correct 1026 ms 11552 KB Output is correct
13 Correct 114 ms 10572 KB Output is correct
14 Correct 1933 ms 12052 KB Output is correct
15 Correct 2007 ms 12076 KB Output is correct
16 Correct 2176 ms 12608 KB Output is correct
17 Correct 3071 ms 13008 KB Output is correct
18 Correct 2433 ms 12624 KB Output is correct
19 Correct 2096 ms 13076 KB Output is correct
20 Correct 2626 ms 13100 KB Output is correct
21 Correct 2661 ms 13260 KB Output is correct