Submission #815415

#	Time	Username	Problem	Language	Result	Execution time	Memory
815415		Cookie	Furniture (JOI20_furniture)	C++14	100 / 100	3351 ms	20924 KiB

furniture

#include<bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("FEEDING.INP");
ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;
using u128 = __uint128_t;
const int x[4] = {1, -1, 0, 0};
const int y[4] = {0, 0, 1, -1};
const ll mod = 1e15 + 7, inf = 1e16;
const int mxn = 2e3 + 5;
int n, m, q;
int a[1005][1005];
int cnt[2005];
bool bad[1005][1005];
bool ck(int x, int y){
    if(x == n && y == m)return(0);
    if(bad[x][y])return(0);
    if(bad[x + 1][y] && bad[x][y + 1])return(1);
    if(bad[x - 1][y] && bad[x][y - 1])return(1);
    return(0);
}
bool inside(int x, int y){
    return(x >= 1 && y >= 1 && x <= n && y <= m);
}
signed main()
{
     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> a[i][j];
            if(a[i][j] == 1){
                bad[i][j] = 1;
            }else{
                cnt[i + j]++;
            }
        }
    }
    for(int i = 1; i <= n; i++)bad[i][m + 1] = 1;
    for(int i = 1; i <= m; i++)bad[n + 1][i] = 1;
    queue<pii>q;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(a[i][j] == 1){
                for(int k = 0; k < 4; k++){
                    if(inside(i + x[k], j + y[k]) && !bad[i + x[k]][j + y[k]]){
                        q.push({i + x[k], j + y[k]});
                    }
                }
            }
        }
    }
    while(!q.empty()){
        auto [cox, coy] = q.front(); q.pop();
        //cout << cox << ' ' << coy << " ";
        if(ck(cox, coy)){
            
            bad[cox][coy] = 1; cnt[cox + coy]--;
            for(int i = 0; i < 4; i++){
                int nwx = cox + x[i], nwy = coy + y[i];
                if(inside(nwx, nwy) && !bad[nwx][nwy]){
                    q.push({nwx, nwy});
                }
            }
        }
    }
    for(int i = 2; i <= n + m; i++){
        assert(cnt[i] >= 1);
    }
    int qq; cin >> qq;
    while(qq--){
        int cox, coy; cin >> cox >> coy;
        if(cnt[cox + coy] == 0){
            cout << cox + coy << "\n";
        }
        if(bad[cox][coy]){
            cout << 1 << "\n";
        }
        else if(cnt[cox + coy] == 1){
            cout << 0 << "\n";
            continue;
        }else{
           
            vt<pii>rem;
            bool ok = 1;
            rem.pb({cox, coy});
            int xx = cox, yy = coy;
            bad[cox][coy] = 1; cnt[cox + coy]--;
            for(int i = 0; i < 4; i++){
                int nwx = cox + x[i], nwy = coy + y[i];
                if(inside(nwx, nwy) && !bad[nwx][nwy]){
                    q.push({nwx, nwy});
                }
            }
            
            while(!q.empty()){
                auto [cox, coy] = q.front(); q.pop();
                
                if(ck(cox, coy)){
                    //assert(cox == xx || cox + coy != xx + yy);
                    bad[cox][coy] = 1; cnt[cox + coy]--;
                    if(cnt[cox+ coy] == 0){
                        ok = 0; 
                    }
                    rem.pb({cox, coy});
                    for(int i = 0; i < 4; i++){
                        int nwx = cox + x[i], nwy = coy + y[i];
                        if(inside(nwx, nwy) && !bad[nwx][nwy]){
                            q.push({nwx, nwy});
                        }
                    }
                }
            }
           if(ok)cout << 1 << "\n";
           else{
               cout << 0 << "\n";
               for(auto [xx, yy]: rem){
                   bad[xx][yy] = 0; cnt[xx + yy]++;
               }
           }
    
        }
    }
    return(0);
}

Compilation message (stderr)

furniture.cpp: In function 'int main()':
furniture.cpp:67:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   67 |         auto [cox, coy] = q.front(); q.pop();
      |              ^
furniture.cpp:110:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  110 |                 auto [cox, coy] = q.front(); q.pop();
      |                      ^
furniture.cpp:130:25: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  130 |                for(auto [xx, yy]: rem){
      |                         ^
furniture.cpp:100:17: warning: unused variable 'xx' [-Wunused-variable]
  100 |             int xx = cox, yy = coy;
      |                 ^~
furniture.cpp:100:27: warning: unused variable 'yy' [-Wunused-variable]
  100 |             int xx = cox, yy = coy;
      |                           ^~

• Subtask 1: 5 / 5
• Subtask 2: 95 / 95