답안 #303455

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
303455 2020-09-20T10:22:39 Z vaaven Furniture (JOI20_furniture) C++14
100 / 100
2858 ms 10368 KB
/*                                                                                                    
                                             `-:://:::-                                             
                                           `//:-------:/:`                                          
                                          .+:--.......--:+`                                         
                                         `+:--..`````..--//`                                        
                                         .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] == '1'){
        q.push(make_pair(cur.first+1, cur.second));
        q.push(make_pair(cur.first, cur.second-1));
      } else if(!okk(cur.first+1, cur.second-1)){
        if(okk(cur.first+1, cur.second))
          q.push(make_pair(cur.first+1, cur.second));
        if(okk(cur.first, cur.second-1))
          q.push(make_pair(cur.first, cur.second-1));
      }
      if(okk(cur.first-1, cur.second+1) && kek[cur.first-1][cur.second+1] == '1'){
        q.push(make_pair(cur.first-1, cur.second));
        q.push(make_pair(cur.first, cur.second+1));
      } else if(!okk(cur.first-1, cur.second+1)){
        if(okk(cur.first-1, cur.second))
          q.push(make_pair(cur.first-1, cur.second));
        if(okk(cur.first, cur.second+1))
          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] == '1'){
        q.push(make_pair(cur.first+1, cur.second));
        q.push(make_pair(cur.first, cur.second-1));
      } else if(!okk(cur.first+1, cur.second-1)){
        if(okk(cur.first+1, cur.second))
          q.push(make_pair(cur.first+1, cur.second));
        if(okk(cur.first, cur.second-1))
          q.push(make_pair(cur.first, cur.second-1));
      }
      if(okk(cur.first-1, cur.second+1) && kek[cur.first-1][cur.second+1] == '1'){
        q.push(make_pair(cur.first-1, cur.second));
        q.push(make_pair(cur.first, cur.second+1));
      } else if(!okk(cur.first-1, cur.second+1)){
        if(okk(cur.first-1, cur.second))
          q.push(make_pair(cur.first-1, cur.second));
        if(okk(cur.first, cur.second+1))
          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();
}
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 9 ms 768 KB Output is correct
3 Correct 11 ms 768 KB Output is correct
4 Correct 21 ms 912 KB Output is correct
5 Correct 23 ms 896 KB Output is correct
6 Correct 28 ms 888 KB Output is correct
7 Correct 27 ms 896 KB Output is correct
8 Correct 32 ms 888 KB Output is correct
9 Correct 27 ms 896 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 9 ms 768 KB Output is correct
3 Correct 11 ms 768 KB Output is correct
4 Correct 21 ms 912 KB Output is correct
5 Correct 23 ms 896 KB Output is correct
6 Correct 28 ms 888 KB Output is correct
7 Correct 27 ms 896 KB Output is correct
8 Correct 32 ms 888 KB Output is correct
9 Correct 27 ms 896 KB Output is correct
10 Correct 71 ms 1152 KB Output is correct
11 Correct 16 ms 640 KB Output is correct
12 Correct 893 ms 9832 KB Output is correct
13 Correct 127 ms 9832 KB Output is correct
14 Correct 2296 ms 10368 KB Output is correct
15 Correct 2398 ms 9632 KB Output is correct
16 Correct 2744 ms 9676 KB Output is correct
17 Correct 2731 ms 10104 KB Output is correct
18 Correct 2727 ms 9848 KB Output is correct
19 Correct 2858 ms 10196 KB Output is correct
20 Correct 2784 ms 10316 KB Output is correct
21 Correct 2769 ms 10232 KB Output is correct