//Judges with GCC >= 12 only needs Ofast
//#pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
//MLE optimization
//#pragma GCC optimize("conserve-stack")
//Old judges
//#pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
//New judges. Test with assert(__builtin_cpu_supports("avx2"));
//#pragma GCC target("arch=skylake")
//Atcoder
//#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
//template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//write variables and debug
#define bugf cout << "Here" << endl
#define bug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#define bugarr(arr,...) cout << #arr; _dbg_arr(arr, __VA_ARGS__)
template<class T, class U>
ostream& operator<<(ostream& output, const pair<T, U> &A){
output << "(" << A.first << ", " << A.second << ")";
return output;
}
template <class T>
ostream& operator<<(ostream& output, const vector<T> &arr){
int n = arr.size();
output << "[";
for(int i = 0; i < n; i++){
output << arr[i];
if(i != n - 1) output << ", ";
}
output << "]";
return output;
}
template<class T>
ostream& operator<<(ostream& output, const set<T> &s){
output << "{";
for(auto it = s.begin(); it != s.end(); it++){
if(it != s.begin()) output << ", ";
output << (*it);
}
output << "}";
return output;
}
template<class T, class U>
ostream& operator<<(ostream& output, const map<T, U> &m){
output << "{";
for(auto it = m.begin(); it != m.end(); it++){
if(it != m.begin()) output << ", ";
output << "(" << it->first << " : " << it->second << ")";
}
output << "}";
return output;
}
template<class TH>
void _dbg(const char *sdbg, TH h){
cout << sdbg << " = " << h << endl;
}
template<class TH, class... TA>
void _dbg(const char *sdbg, TH h, TA... a) {
while(*sdbg != ',')cout << *sdbg++;
cout << " = " << h << "\n";
_dbg(sdbg+1, a...);
}
template<class _Arr, class _Index>
void _dbg_arr(_Arr arr, _Index index){
cout << '[' << index << "] = " << arr[index] << endl;
}
template<class _Arr, class _Index, class... TA>
void _dbg_arr(_Arr &arr, _Index index, TA... args){
cout << '[' << index << ']';
_dbg_arr(arr[index], args...);
}
//open file
#define taskname "" //name input and output file
#ifdef SteGG
void open(){
if(fopen("input.inp", "r")){
freopen("input.inp", "r", stdin);
freopen("output.out", "w", stdout);
}
}
#else
void open(){
if(fopen(taskname".inp", "r")){
freopen(taskname".inp", "r", stdin);
freopen(taskname".out", "w", stdout);
}
}
#endif
//initialize
#define testcase \
long long test; \
cin >> test; \
for(int tst = 1; tst <= test; tst++)
#define int long long
#define MOD 1000000007
#define FFTMOD (119 << 23 | 1)
#define EPSILON 1e-9
#define setpre(x) fixed << setprecision(x)
#define cd complex<double>
#define all(x) x.begin(), x.end()
const long long INF = 3e18L + 5;
const int inf = 1e9 + 7;
const double infd = 1e60;
const double PI = acos(-1);
const int maxn = 1e5 + 5;
//const int base = ;
int n, m;
int board[1001][1001];
int ceho[maxn];
int q;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
//others struct or class
//others function
//others init
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
open();
cin >> n >> m;
auto isvalid = [&](int x, int y){
if(x < 1 || y < 1 || x > n || y > m || board[x][y]) return false;
return true;
};
auto check = [&](int x, int y){
if((x == 1 && y == 1) || (x == n && y == m)) return false;
if((x == 1 || board[x - 1][y]) && (y == 1 || board[x][y - 1])) return true;
if((x == n || board[x + 1][y]) && (y == m || board[x][y + 1])) return true;
return false;
};
auto dfs = [&](auto &&dfs, int x, int y) -> void {
board[x][y] = true;
ceho[x + y]--;
for(int k = 0; k < 4; k++){
int new_x = x + dx[k];
int new_y = y + dy[k];
if(isvalid(new_x, new_y) && check(new_x, new_y)) dfs(dfs, new_x, new_y);
}
};
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
ceho[i + j] ++;
if(board[i][j] == 1){
cin >> board[i][j];
board[i][j] = 1;
continue;
}
cin >> board[i][j];
if(board[i][j]){
dfs(dfs, i, j);
}
}
}
cin >> q;
while(q--){
int x, y;
cin >> x >> y;
if(board[x][y]){
cout << 1 << endl;
}else if(ceho[x + y] == 1){
cout << 0 << endl;
}else{
dfs(dfs, x, y);
cout << 1 << endl;
}
}
return 0;
}
Compilation message
furniture.cpp: In function 'void open()':
furniture.cpp:101:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
101 | freopen(taskname".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
furniture.cpp:102:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
102 | freopen(taskname".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
596 KB |
Output is correct |
| 2 |
Correct |
4 ms |
724 KB |
Output is correct |
| 3 |
Correct |
5 ms |
724 KB |
Output is correct |
| 4 |
Correct |
9 ms |
724 KB |
Output is correct |
| 5 |
Correct |
10 ms |
824 KB |
Output is correct |
| 6 |
Correct |
12 ms |
724 KB |
Output is correct |
| 7 |
Correct |
12 ms |
808 KB |
Output is correct |
| 8 |
Correct |
12 ms |
724 KB |
Output is correct |
| 9 |
Correct |
12 ms |
820 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
596 KB |
Output is correct |
| 2 |
Correct |
4 ms |
724 KB |
Output is correct |
| 3 |
Correct |
5 ms |
724 KB |
Output is correct |
| 4 |
Correct |
9 ms |
724 KB |
Output is correct |
| 5 |
Correct |
10 ms |
824 KB |
Output is correct |
| 6 |
Correct |
12 ms |
724 KB |
Output is correct |
| 7 |
Correct |
12 ms |
808 KB |
Output is correct |
| 8 |
Correct |
12 ms |
724 KB |
Output is correct |
| 9 |
Correct |
12 ms |
820 KB |
Output is correct |
| 10 |
Correct |
29 ms |
852 KB |
Output is correct |
| 11 |
Correct |
7 ms |
596 KB |
Output is correct |
| 12 |
Correct |
389 ms |
8780 KB |
Output is correct |
| 13 |
Correct |
57 ms |
7884 KB |
Output is correct |
| 14 |
Correct |
954 ms |
9320 KB |
Output is correct |
| 15 |
Correct |
985 ms |
9356 KB |
Output is correct |
| 16 |
Correct |
1097 ms |
9664 KB |
Output is correct |
| 17 |
Correct |
1114 ms |
10284 KB |
Output is correct |
| 18 |
Correct |
1097 ms |
9832 KB |
Output is correct |
| 19 |
Correct |
1149 ms |
10360 KB |
Output is correct |
| 20 |
Correct |
1146 ms |
10212 KB |
Output is correct |
| 21 |
Correct |
1139 ms |
10148 KB |
Output is correct |
