#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
int n, m;
struct Map{
int x, y;
vector<vector<int>> ref;
vector<bool> ac;
vector<pii> pos_ref;
vector<set<int>> lines;
//vector<int> first_lines;
vector<set<int>> cols;
//vector<int> first_cols;
vector<pii> neigs(pii pos){
vector<pii> res;
int i= pos.first;
int j = pos.second;
for(int di = -1; di<2; di++){
for(int dj = -1; dj<2; dj++){
if(di!=0|| dj!=0){
if(di+i<x && dj+j<y && di+i>=0 && dj+j>=0){
if(ref[di+i][dj+j]!=-1){
res.push_back(pii(di+i, dj+j));
}
}
}
}
}
return res;
}
vector<pii> spread(pii pos){
int i = pos.first;
int j = pos.second;
vector<pii> r;
auto it = lines[i].lower_bound(j);
if(it != lines[i].begin()){
r.push_back(pii(i, *(--it)));
}
it = cols[j].lower_bound(i);
if(it!=cols[j].begin()){
r.push_back(pii(*(--it), j));
}
if(i+1<x){
it = lines[i+1].lower_bound(j);
if(it != lines[i+1].begin() && lines[i+1].size()>0){
r.push_back(pii( i+1, *(--it)));
}
}
if(j+1<y){
//cout<<"cols "<<j+1<<" "<<cols[j+1].size()<<endl;
it =cols[j+1].lower_bound(i);
if(it !=cols[j+1].begin() && cols[j+1].size()>0){
r.push_back(pii(*(--it), j+1));
}
}
return r;
}
vector<pii> rev_spread(pii pos){
int i = pos.first;
int j = pos.second;
vector<pii> r;
auto it = lines[i].upper_bound(j);
if(it != lines[i].end()){
r.push_back(pii(i,*it));
}
it = cols[j].upper_bound(i);
if(it!=cols[j].end()){
r.push_back(pii(*it, j));
}
if(i-1>=0){
it = lines[i-1].upper_bound(j);
if(it != lines[i-1].end()){
r.push_back(pii(i-1, *(it)));
}
}
if(j-1>=0){
//cout<<"cols "<<j-1<<" "<<cols[j-1].size()<<endl;
it =cols[j-1].upper_bound(i);
if(it !=cols[j-1].end()){
r.push_back(pii(*it, j-1));
}
}
//cout<<"spread size"<<r.size()<<endl;
return r;
}
void dfs(int i, int j){
//cout<<"dfs "<<i<<" "<<j<<endl;
ac[ref[i][j]] = true;
for(auto e: neigs(pii(i, j))){
if(ref[e.first][e.second]!=-1){
//cout<<e.first<<" "<<e.second<<endl;
//cout<<ref[e.first][e.second]<<endl;
if(!ac[ref[e.first][e.second]]){
//cout<<"here"<<endl;
dfs(e.first, e.second);
}
}
}
//cout<<"none"<<endl;
for(auto e: spread(pii(i, j))){
//cout<<e.first<<" "<<e.second<<endl;
if(!ac[ref[e.first][e.second]]){
dfs(e.first, e.second);
}
}
}
Map(){};
void display(){
for(int i = 0; i<x; i++){
for(int j = 0; j<y; j++){
if(ref[i][j] ==-1){
//cout<<"O";
}
else{
if(ac[ref[i][j]]){
//cout<<"#";
}
else{
//cout<<"W";
}
}
}
//cout<<endl;
}
}
Map(vector<vector<bool>>& f){
x=f.size()+1;
y = f[0].size()+1;
lines.resize(x);
cols.resize(y);
ref.resize(x, vector<int> (y, -1));
for(int i = 0; i<x; i++){
for(int j = 0; j<y; j++){
if(i==0|| j==0){
ref[i][j] = ac.size();
ac.push_back(true);
pos_ref.push_back(pii(i, j));
lines[i].insert(j);
cols[j].insert(i);
}
else{
if(f[i-1][j-1]){
ref[i][j] = ac.size();
ac.push_back(false);
pos_ref.push_back(pii(i, j));
lines[i].insert(j);
cols[j].insert(i);
}
}
}
}
for(int i = 0; i<ac.size(); i++){
if(ac[i]){
dfs(pos_ref[i].first, pos_ref[i].second);
}
}
display();
}
bool try_insert(pii pos){
int i = pos.first;
int j = pos.second;
bool ok = false;
//cout<<"trying "<<pos.first<<" "<<pos.second<<endl;
for(auto e: neigs(pos)){
ok|= ac[ref[e.first][e.second]];
}
for(auto e: rev_spread(pos)){
ok|= ac[ref[e.first][e.second]];
}
return ok;
}
void insert(pii pos){
int i =pos.first;
int j = pos.second;
ref[i][j] = ac.size();
ac.push_back(try_insert(pos));
pos_ref.push_back(pii(i, j));
lines[i].insert(j);
cols[j].insert(i);
if(ac.back()){
dfs(i, j);
}
}
}maps[2];
vector<vector<bool>> rotate(vector<vector<bool>> a){
vector<vector<bool>> b(a[0].size(), vector<bool>(a.size()));
for(int i = 0; i<a.size(); i++){
for(int j = 0; j<b.size(); j++){
b[j][a.size()-i-1] = a[i][j];
}
}
return b;
}
signed main(){
cin>>n>>m;
vector<vector<bool>> a(n, vector<bool> (m));
for(int i = 0; i<n; i++){
for(int j = 0; j<m; j++){
int c;
cin>>c;
a[i][j] = (c==1);
}
}
auto b = rotate(a);
auto c= rotate(rotate(b));
maps[0]= Map(b);
maps[1] = Map(c);
maps[0].display();
maps[1].display();
int q;
cin>>q;
for(int i = 0; i<q; i++){
int a, b;
cin>>a>>b;
bool ok =maps[0].try_insert(pii(b, n-a+1));
ok&= maps[1].try_insert(pii(m-b+1, a));
if(ok){
cout<<0<<endl;
}
else{
cout<<1<<endl;
maps[0].insert(pii(b, n-a+1));
maps[1].insert(pii(m-b+1, a));
}
}
}
Compilation message
furniture.cpp: In constructor 'Map::Map(std::vector<std::vector<bool> >&)':
furniture.cpp:172:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
172 | for(int i = 0; i<ac.size(); i++){
| ~^~~~~~~~~~
furniture.cpp: In member function 'bool Map::try_insert(std::pair<long long int, long long int>)':
furniture.cpp:182:13: warning: unused variable 'i' [-Wunused-variable]
182 | int i = pos.first;
| ^
furniture.cpp:183:13: warning: unused variable 'j' [-Wunused-variable]
183 | int j = pos.second;
| ^
furniture.cpp: In function 'std::vector<std::vector<bool> > rotate(std::vector<std::vector<bool> >)':
furniture.cpp:216:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
216 | for(int i = 0; i<a.size(); i++){
| ~^~~~~~~~~
furniture.cpp:217:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
217 | for(int j = 0; j<b.size(); j++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
596 KB |
Output is correct |
| 2 |
Correct |
15 ms |
1276 KB |
Output is correct |
| 3 |
Correct |
24 ms |
1548 KB |
Output is correct |
| 4 |
Correct |
33 ms |
2472 KB |
Output is correct |
| 5 |
Correct |
47 ms |
2568 KB |
Output is correct |
| 6 |
Correct |
45 ms |
2728 KB |
Output is correct |
| 7 |
Correct |
37 ms |
2756 KB |
Output is correct |
| 8 |
Correct |
42 ms |
2864 KB |
Output is correct |
| 9 |
Correct |
35 ms |
2772 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
596 KB |
Output is correct |
| 2 |
Correct |
15 ms |
1276 KB |
Output is correct |
| 3 |
Correct |
24 ms |
1548 KB |
Output is correct |
| 4 |
Correct |
33 ms |
2472 KB |
Output is correct |
| 5 |
Correct |
47 ms |
2568 KB |
Output is correct |
| 6 |
Correct |
45 ms |
2728 KB |
Output is correct |
| 7 |
Correct |
37 ms |
2756 KB |
Output is correct |
| 8 |
Correct |
42 ms |
2864 KB |
Output is correct |
| 9 |
Correct |
35 ms |
2772 KB |
Output is correct |
| 10 |
Correct |
116 ms |
8448 KB |
Output is correct |
| 11 |
Correct |
25 ms |
1956 KB |
Output is correct |
| 12 |
Correct |
3222 ms |
96660 KB |
Output is correct |
| 13 |
Correct |
337 ms |
43592 KB |
Output is correct |
| 14 |
Execution timed out |
5062 ms |
145092 KB |
Time limit exceeded |
| 15 |
Halted |
0 ms |
0 KB |
- |
