Submission #303417

#	Time	Username	Problem	Language	Result	Execution time	Memory
303417		vaaven	Furniture (JOI20_furniture)	C++14	0 / 100	6 ms	1408 KiB

furniture

/*                                                                                                    
                                             `-:://:::-                                             
                                           `//:-------:/:`                                          
                                          .+:--.......--:+`                                         
                                         `+:--..`````..--//`                                        
                                         .o:--..`` ``..--:o`                                        
                                         .o:--...```..---+/`                                        
                                       `/y+o/---....---:+o.                                         
                                   `...````-os+/:---:/+o/--.`                                       
              `-/+++++/:.      `...`       :h+d+oooo+/+-`   ...                                     
            `/++//:::://++-`....`         -.`//````````:`     `..`                                  
           `o+/::------://o/`           `-` -.          -`       `..`                               
  `....o+:-++/:--.```..-://s.        `-`  .-              -`          `-o: .-//::::/:-`             
          `:s+/:--....-::/+s-`      .-   `-                -`           -///:--------:/:`           
            .:ooo+++++osso-`    `.:-...`/` ./::-------:/:`   -`         :+--..``````.--:+:...-+:-`  
             `.-/+++++/+-.-`    -.   ``:so:/:--.......--:+`  `-```````o+/+--..`````..--:o/-..:s+:.  
                 ```````:``.. `-`     -` `+:--..`````..--/+-.../.`````..-o:--.......---/o.    `     
                        `:  `:-      -.  .o:--..`` ``..--:o`   `-`      `:o+:--------:+o-`          
                         `-`-...    ..   .o/--...```..--:+/`    `-`     `oy/so/////++o/.`           
                          -/`  `-` `- ``+s/o/:---...---:++.      `-`   .-../d://///:-.`             
                `.---..``-..-    .-/..`````-oo+/:::::/+o+-        `-``-`  `-.  ````                 
             `:++++/+++++-  ..``.-/:`      /y-:/++o++/:.`..`       ./.   `-                         
            -++/::::::://+/..:-``:` ..   `-.`  ```.```    `..`   `..`-` `-                          
       ``  -o//:--....-::/++` -.-`   `-`.-`                 `..`..`  `-.-                           
  -----ss+:++/:--.```..-://s.  /.     `::                    `-:.     ./`                           
  `````/:..+o/::-..``.--:/+s. ..-`   `-``-`                 ..` `-`  `-`-`                          
          `-s+/::-----::/+oo---``-` ..    .:-    ```      .-`     .-.-  `-`                         
           `:oo+//::://+os/..:`..-/:`      :y.-:::::::.`.-`        ./-`  `-`                        
            `./+oooooooo+/.`-    .-:...`.. .//:-------://`        `- `..` `:.                       
              ``.-::::-.``-/`  `-` `-  `oo:+:--.......--:/`      `-    `.:--h.``..```               
                          -.-`.-    .-   `+:--..`````..--//`    `-       /s-//::::::::.             
                         -` `/-      ..  .o:--..`` ``..--:o.```.-        `//:--------://`           
                        -` .-`.-`     -.`-o/--...```..--:+/.``-:....``:-.+:--....`...--:+`          
                       ..`-.   `-.   ``:os:o/:---...---:++.  `-     ``///+:-..``````.--:+-````-.`   
              `.:///////.-`      .:-..` -``-+o+/:::::/+o/.  `-         `:+:-..`````..--:o/:--/ys+-  
            `-++///////+o/. ``....`-.    :` `.:++++++/:.`  .-           -o/---......---/o.   `.`    
           `++//:-----::/+o:..`     .-`   :    ```````    .-           `+so+:--------:++-`          
  `````:-``:o/::-..`..--:/+o`         -.  `-             .-          `../../+o+////+o+:.`           
  -----syo/o+/:--.```..-://s.          .-` `-           .-        `...     ``-:////:-``             
       .` `/s//:--....-::/+s.            -. `-`        .-       `..`                                
           .+o+/:::--:://+s/-..`          .::+y  ```  .-     `..`                                   
            ./oo++////+oso-`   `....       :y-+:::::::/`   ...                                      
             `.:+oooooo/-`         `....-. .//:-------:/:-.`                                        
                ``...``                 /+:+:--.......--:+`                                         
                                         `+:--..`````..--//`                                        
                                         .o:--..`` ``..--:o`                                        
                                         .+/--...```..--:+/`                                        
                                         `-o/:---...---:++.                                         
                                          `-+o+/:---:/+o/.                                          
                                            `.:+oooo+/-.`                                           
                                               ``````                                               
*/
// #pragma GCC optimize("Ofast,no-stack-protector")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC optimize("fast-math")
// #pragma GCC optimize("section-anchors")
// #pragma GCC optimize("profile-values,profile-reorder-functions,tracer")
// #pragma GCC optimize("vpt")
// #pragma GCC optimize("rename-registers")
// #pragma GCC optimize("move-loop-invariants")
// #pragma GCC optimize("unswitch-loops")
// #pragma GCC optimize("function-sections")
// #pragma GCC optimize("data-sections")
// #pragma GCC optimize("branch-target-load-optimize")
// #pragma GCC optimize("branch-target-load-optimize2")
// #pragma GCC optimize("btr-bb-exclusive")
// #pragma comment(linker, "/STACK:367077216")
#include <iostream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <tuple>
#include <math.h>
#include <set>
#include <stack>
#include <bitset>
#include <map>
#include <queue>
#include <random>
#include <unordered_set>
#include <unordered_map>
#define DEBUG
#define fi first
#define se second
#define pqueue priority_queue
#define pb(x) push_back(x)
//#define endl '\n'
#define all(x) x.begin(), x.end()
#define int long  long
#define mk(a, b) make_pair(a, b)
 
using namespace std;
      
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ull> vull;
typedef vector<ll> vll;
// typedef tuple<ll, ll, ll> tiii;
typedef pair<int, int> pii;
typedef vector<pair<int, int> > vpii;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector< vector<ll> > vvll;
typedef vector<char> vc;
      
const int inf = 1e9 + 228;
const ll infll = 1e18;
const ll MOD = 1e9 + 7;
//static const int maxn = 1e6 + 228;
const ld eps = 1e-5;
const int K = 31;
const ld eps2 = 1e-9;
const ll MOD2 = 998244353;
const ll dosz = 5e5;
const ll SZ = (1<<18);
const ld PI = 3.1415926535;
     
void fast_io(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  // freopen("a.in", "r", stdin);
  // freopen("digit.out", "w", stdout);
}

int n, m;
const int maxn = 1001;
int kek[maxn][maxn];
bool okk(int a, int b){
 return !(a<0 || a>=n || b<0 || b>=m);
}

void solve(){ 
  cin >> n >> m;
  vpii to_check;
  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      int t;
      cin >> t;
      kek[i][j] = '0';
      if(t==1){
        to_check.pb(make_pair(i, j));
      }
    } 
  }
  vi good(n+m+228, 0);
  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      good[i+j]++;
    }
  }
  for(pii i:to_check){
    queue<pii> q;
    q.push(i);
    if(kek[i.first][i.second] == '0' && good[i.first + i.second] == 1){
      continue;
    }
    while(!q.empty()){
      pii cur = q.front();
      q.pop();
      if(kek[cur.first][cur.second] == '1')
        continue;
      good[cur.first + cur.second]--;
      kek[cur.first][cur.second] = '1';
      if(okk(cur.first+1, cur.second-1) && kek[cur.first+1][cur.second-1]){
        q.push(make_pair(cur.first+1, cur.second));
        q.push(make_pair(cur.first, cur.second+1));
      }
      if(okk(cur.first-1, cur.second+1) && kek[cur.first-1][cur.second+1]){
        q.push(make_pair(cur.first-1, cur.second));
        q.push(make_pair(cur.first, cur.second-1));
      }
    }
  }
  int q;
  cin >> q;
  for(int _=0; _<q; _++){
    pii i;
    cin >> i.first >> i.second;
    i.second--;
    i.first--;
    queue<pii> q;
    q.push(i);
    if(kek[i.first][i.second] == '0' && good[i.first + i.second] == 1){
      cout << 0 << endl;
      continue;
    }
    while(!q.empty()){
      pii cur = q.front();
      q.pop();
      if(kek[cur.first][cur.second] == '1')
        continue;
      good[cur.first + cur.second]--;
      kek[cur.first][cur.second] = '1';
      if(okk(cur.first+1, cur.second-1) && kek[cur.first+1][cur.second-1]){
        q.push(make_pair(cur.first+1, cur.second));
        q.push(make_pair(cur.first, cur.second+1));
      }
      if(okk(cur.first-1, cur.second+1) && kek[cur.first-1][cur.second+1]){
        q.push(make_pair(cur.first-1, cur.second));
        q.push(make_pair(cur.first, cur.second-1));
      }
    }
    cout << 1 << endl;
  }
}

signed main(){
    fast_io();
    srand(time(NULL));
    // cout << fixed << setprecision(3);
    int q = 1;
    // cin >> q;
    while(q--)
        solve();
}

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