oj.uz

답안 #715650

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
715650 2023-03-27T12:04:45 Z Makarooni Furniture (JOI20_furniture) C++17
100 / 100
 534 ms 61156 KB 
#include "bits/stdc++.h"
using namespace std;

#define all(x) x.begin(), x.end()
#define pb(x) push_back(x)
#define endl '\n'
#define sz(x) (int)x.size()
#define mr(x, y) make_pair(x, y)
#define F first
#define S second

const int N = 2e3 + 10;
const int MOD = 1e9 + 7;

int c[N][N], x[N][N], y[N][N], n, m, cnt[N * 2];
priority_queue<pair<int, int>> st, st2;
bool bl[N][N];

int f(int i, int j){
    return (i - 1) * m + j;
}

void upd(int i, int j){
    if(bl[i][j])
        return;
    bl[i][j] = 1;
    cnt[i + j]--;
    if(i - 1 > 0 && !bl[i - 1][j]){
        x[i - 1][j]--;
        st.push(mr(-x[i - 1][j], f(i - 1, j)));
    }
    if(j - 1 > 0 && !bl[i][j - 1]){
        x[i][j - 1]--;
        st.push(mr(-x[i][j - 1], f(i, j - 1)));
    }
    if(i + 1 <= n && !bl[i + 1][j]){
        y[i + 1][j]--;
        st2.push(mr(-y[i + 1][j], f(i + 1, j)));
    }
    if(j + 1 <= m && !bl[i][j + 1]){
        y[i][j + 1]--;
        st2.push(mr(-y[i][j + 1], f(i, j + 1)));
    }
}

int main(){
    ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    bl[1][1] = 1;
    bl[n][m] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(i == j && i == 1)
                continue;
            if(i == n && j == m)
                continue;
            y[i][j] = (i - 1 > 0) + (j - 1 > 0);
            x[i][j] = (i + 1 <= n) + (j + 1 <= m);
            cnt[i + j]++;
            st.push(mr(-x[i][j], f(i, j)));
            st2.push(mr(-y[i][j], f(i, j)));
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> c[i][j];
            if(!c[i][j])
                continue;
            upd(i, j);
        }
    }
    while(min(-st.top().F, -st2.top().F) == 0){
        if(st.top().F == 0){
            int r = st.top().S, t;
            t = r % m;
            if(t == 0)
                t = m;
            st.pop();
            upd(r / m + (t != m), t);
        }
        else{
            int r = st2.top().S, t;
            t = r % m;
            if(t == 0)
                t = m;
            st2.pop();
            upd(r / m + (t != m), t);
        }
    }
    int p, q, Q;
    cin >> Q;
    while(Q--){
        cin >> p >> q;
        if(bl[p][q])
            cout << 1 << endl;
        else if(cnt[p + q] == 1)
            cout << 0 << endl;
        else{
            cout << 1 << endl;
            upd(p, q);
            while(min(-st.top().F, -st2.top().F) == 0){
                if(st.top().F == 0){
                    int r = st.top().S, t;
                    t = r % m;
                    if(t == 0)
                        t = m;
                    st.pop();
                    upd(r / m + (t != m), t);
                }
                else{
                    int r = st2.top().S, t;
                    t = r % m;
                    if(t == 0)
                        t = m;
                    st2.pop();
                    upd(r / m + (t != m), t);
                }
            }
        }
    }
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1620 KB Output is correct
2 Correct 3 ms 2004 KB Output is correct
3 Correct 4 ms 2132 KB Output is correct
4 Correct 5 ms 2132 KB Output is correct
5 Correct 6 ms 2260 KB Output is correct
6 Correct 6 ms 2272 KB Output is correct
7 Correct 6 ms 2272 KB Output is correct
8 Correct 5 ms 2360 KB Output is correct
9 Correct 6 ms 2260 KB Output is correct

Subtask #2
95.0 / 95.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1620 KB Output is correct
2 Correct 3 ms 2004 KB Output is correct
3 Correct 4 ms 2132 KB Output is correct
4 Correct 5 ms 2132 KB Output is correct
5 Correct 6 ms 2260 KB Output is correct
6 Correct 6 ms 2272 KB Output is correct
7 Correct 6 ms 2272 KB Output is correct
8 Correct 5 ms 2360 KB Output is correct
9 Correct 6 ms 2260 KB Output is correct
10 Correct 19 ms 3776 KB Output is correct
11 Correct 5 ms 1492 KB Output is correct
12 Correct 358 ms 53516 KB Output is correct
13 Correct 191 ms 50020 KB Output is correct
14 Correct 455 ms 55628 KB Output is correct
15 Correct 449 ms 54252 KB Output is correct
16 Correct 434 ms 56788 KB Output is correct
17 Correct 484 ms 59804 KB Output is correct
18 Correct 486 ms 58960 KB Output is correct
19 Correct 529 ms 61128 KB Output is correct
20 Correct 486 ms 61152 KB Output is correct
21 Correct 534 ms 61156 KB Output is correct