Submission #1227624

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227624		minhpk	Furniture (JOI20_furniture)	C++20	100 / 100	490 ms	76884 KiB

furniture

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,b;
int r[2001][2001];

set<pair<int,int>> s[2002];

signed main()
{
//    freopen("test.txt", "r", stdin);
//    freopen("o2.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a >> b;
    for (int i=1;i<=a;i++){
         for (int j=1;j<=b;j++){
              int x;
              cin >> x;
              if (x==1){
                  r[i][j]=1;
              }
         }
    }
    for (int i=1;i<=b;i++){
         r[0][i]=1;
         r[a+1][i]=1;
    }
    for (int i=1;i<=a;i++){
         r[i][0]=1;
         r[i][b+1]=1;
    }
    for (int i=1;i<=a;i++){
         for (int j=1;j<=b;j++){
             if (i==1 && j==1){
                 continue;
             }
              if (r[i-1][j] && r[i][j-1]){
                  r[i][j]=1;
              }
         }
    }
    for (int i=a;i>=1;i--){
         for (int j=b;j>=1;j--){
               if (i==a && j==b){
                 continue;
               }
              if (r[i][j+1] && r[i+1][j]){
                  r[i][j]=1;
              }
         }
    }

    for (int i=1;i<=a;i++){
         for (int j=1;j<=b;j++){
              if (r[i][j]==0){
                  s[i+j].insert({i,j});
              }
         }
    }
    int q1;
    cin >> q1;
    while (q1--){
         int x,y;
         cin >> x >> y;
         if (r[x][y]){
             cout << 1 << "\n";
         }else{
             if (s[x+y].size()>1){
                 cout << 1 << "\n";
                 auto it=s[x+y].find({x,y});
                 s[x+y].erase(it);
                 r[x][y]=1;
                 queue<pair<int,int>> q;
                 q.push({x,y});
                 while (q.size()){
                      pair<int,int> pos=q.front();
                      q.pop();
                      x=pos.first;
                      y=pos.second;
                      if (r[x+1][y-1] && !r[x+1][y]){
                        auto it1=s[x+y+1].find({x+1,y});
                        s[x+y+1].erase(it1);
                        r[x+1][y]=1;
                        q.push({x+1,y});
                     }
                 if (r[x-1][y+1] && !r[x][y+1]){
                     auto it1=s[x+y+1].find({x,y+1});
                     s[x+y+1].erase(it1);
                     r[x][y+1]=1;
                     q.push({x,y+1});
                 }
                 if (r[x+1][y-1] && !r[x][y-1]){
                     auto it1=s[x+y-1].find({x,y-1});
                     s[x+y-1].erase(it1);
                     r[x][y-1]=1;
                     q.push({x,y-1});
                 }
                    if (r[x-1][y+1] && !r[x-1][y]){
                     auto it1=s[x+y-1].find({x-1,y});
                     s[x+y-1].erase(it1);
                     r[x-1][y]=1;
                     q.push({x-1,y});
                    }
                 }
             }else{
                 cout << 0 << "\n";
             }
         }


//         cout << "\n";
//         for (int i=1;i<=a;i++){
//         for (int j=1;j<=b;j++){
//             cout << r[i][j] << " ";
//         }
//         cout << "\n";
//         }
    }
    return 0;
}


/*
9 11
2 1
3 2
4 1
5 1
6 1
7 5
8 6
9 4
2
1
3
5
4
4
4
5
4
4
2 5
1 8 3 6
1 5 4 3
2 6




9 20
2 1
3 1
4 1
5 1
6 1
7 6
8 6
9 7
4
2
2
2
5
2
3
3
3
5
1 7 3 3
2 3
1 6 7 6
1 2 5 2
1 6 7 0


9 7
2 1
3 1
4 2
5 3
6 1
7 3
8 6
9 6
2
1
5
3
3
1
1
3
1
3
1 7 3 6
2 7
2 5

*/






/*
5
10 9 3 6 1
3
2 1 2 4
1 2 4
1 2 2



5
2 8 6 4 1
4
3 1 2 9
1 1 3
2 1 4 5
1 2 5
*/





/*
8
01010101
10111000


8
01010101
10111000
10101010


6
110110
011101


001001


8
01010101
11000010

10101010
*/



/*
freopen("test.txt", "r", stdin);
    freopen("o2.out", "w", stdout);
*/

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