답안 #683918

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
683918 2023-01-19T16:19:42 Z victor_gao Furniture (JOI20_furniture) C++17
100 / 100
338 ms 23476 KB
#pragma GCC optimize("Ofast,unroll-loops,O3")
#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define pii pair<int,int>
#define x first
#define y second
#define N 1015
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
int g[2*N];
int n,m,arr[N][N],in[N][N],out[N][N];
bool vis[N][N];
bool check(int x,int y){
    arr[x][y]=1;
    if (vis[x][y]) return 1;
    bool ok=1;
    vector<pii>path,path2;
    queue<pii>q;
    q.push({x,y});
    vis[x][y]=1;
    g[x+y]--;
    path.push_back({x,y});
    if (!g[x+y]) ok=0;
    while (!q.empty()&&ok){
        pii np=q.front(); q.pop();
        path2.push_back(np);
        if (np.x+1<=n&&!vis[np.x+1][np.y]){
            in[np.x+1][np.y]--;
            if (!in[np.x+1][np.y]){
                q.push({np.x+1,np.y});
                vis[np.x+1][np.y]=1;
                g[np.x+np.y+1]--;
                path.push_back({np.x+1,np.y});
            }
        }
        if (np.y+1<=m&&!vis[np.x][np.y+1]){
            in[np.x][np.y+1]--;
            if (!in[np.x][np.y+1]){
                q.push({np.x,np.y+1});
                vis[np.x][np.y+1]=1;
                g[np.x+np.y+1]--;
                path.push_back({np.x,np.y+1});
            }
        }
        if (g[np.x+np.y+1]==0) ok=0;
    }
    if (ok){
        for (auto [i,j]:path){
            if (i-1>0&&!vis[i-1][j]){
                out[i-1][j]--;
                if (!out[i-1][j])
                    q.push({i-1,j});
            }
            if (j-1>0&&!vis[i][j-1]){
                out[i][j-1]--;
                if (!out[i][j-1])
                    q.push({i,j-1});
            }
        }
        while (!q.empty()){
            auto [i,j]=q.front(); q.pop();
            vis[i][j]=1;
            g[i+j]--;
            if (i-1>0&&!vis[i-1][j]){
                out[i-1][j]--;
                if (!out[i-1][j])
                    q.push({i-1,j});
            }
            if (j-1>0&&!vis[i][j-1]){
                out[i][j-1]--;
                if (!out[i][j-1])
                    q.push({i,j-1});
            }
        }
        return ok;
    } 
    else {
        arr[x][y]=0;
        for (auto i:path){
            vis[i.x][i.y]=0;
            g[i.x+i.y]++;
        }
        for (auto [i,j]:path2){
            if (j+1<=m&&arr[i][j+1]==0&&!vis[i][j+1])
                in[i][j+1]++;
            if (i+1<=n&&arr[i+1][j]==0&&!vis[i+1][j])
                in[i+1][j]++;
        }
        return 0;
    }
}
signed main(){
    fast
    cin>>n>>m;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            cin>>arr[i][j];
            g[i+j]++;
        }
    }
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            if (j+1<=m){
                out[i][j]++;
                in[i][j+1]++;
            }
            if (i+1<=n){
                out[i][j]++;
                in[i+1][j]++;
            }
        }
    }
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            if (arr[i][j])
                check(i,j);
        }
    }
    int q; cin>>q;
    while (q--){
        int x,y; cin>>x>>y;
        /*
        for (int i=1;i<=n;i++){
            for (int j=1;j<=m;j++){
                cout<<vis[i][j];
            }
            cout<<'\n';
        }
        cout<<'\n';
        for (int i=1;i<=n;i++){
            for (int j=1;j<=m;j++){
                cout<<in[i][j]<<" ";
            }
            cout<<'\n';
        }
        cout<<'\n';
        */
        int ans=check(x,y);
        cout<<ans<<'\n';
    }
}

Compilation message

furniture.cpp:2:88: warning: bad option '-favx' to pragma 'optimize' [-Wpragmas]
    2 | #pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
      |                                                                                        ^
furniture.cpp:2:88: warning: bad option '-favx2' to pragma 'optimize' [-Wpragmas]
furniture.cpp:2:88: warning: bad option '-fsse' to pragma 'optimize' [-Wpragmas]
furniture.cpp:2:88: warning: bad option '-fsse2' to pragma 'optimize' [-Wpragmas]
furniture.cpp:2:88: warning: bad option '-fsse3' to pragma 'optimize' [-Wpragmas]
furniture.cpp:2:88: warning: bad option '-fssse3' to pragma 'optimize' [-Wpragmas]
furniture.cpp:2:88: warning: bad option '-fsse4' to pragma 'optimize' [-Wpragmas]
furniture.cpp:2:88: warning: bad option '-fpopcnt' to pragma 'optimize' [-Wpragmas]
furniture.cpp:2:88: warning: bad option '-fabm' to pragma 'optimize' [-Wpragmas]
furniture.cpp:2:88: warning: bad option '-fmmx' to pragma 'optimize' [-Wpragmas]
furniture.cpp:2:88: warning: bad option '-ffma' to pragma 'optimize' [-Wpragmas]
furniture.cpp:2:88: warning: bad option '-ftune=native' to pragma 'optimize' [-Wpragmas]
furniture.cpp:19:23: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
   19 | bool check(int x,int y){
      |                       ^
furniture.cpp:19:23: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
furniture.cpp:19:23: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
furniture.cpp:19:23: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
furniture.cpp:19:23: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
furniture.cpp:19:23: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
furniture.cpp:19:23: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
furniture.cpp:19:23: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
furniture.cpp:19:23: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
furniture.cpp:19:23: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
furniture.cpp:19:23: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
furniture.cpp:19:23: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
furniture.cpp:98:13: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
   98 | signed main(){
      |             ^
furniture.cpp:98:13: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
furniture.cpp:98:13: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
furniture.cpp:98:13: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
furniture.cpp:98:13: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
furniture.cpp:98:13: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
furniture.cpp:98:13: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
furniture.cpp:98:13: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
furniture.cpp:98:13: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
furniture.cpp:98:13: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
furniture.cpp:98:13: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
furniture.cpp:98:13: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1236 KB Output is correct
2 Correct 2 ms 1620 KB Output is correct
3 Correct 2 ms 1492 KB Output is correct
4 Correct 3 ms 1492 KB Output is correct
5 Correct 5 ms 1676 KB Output is correct
6 Correct 4 ms 1672 KB Output is correct
7 Correct 4 ms 1620 KB Output is correct
8 Correct 3 ms 1632 KB Output is correct
9 Correct 4 ms 1620 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1236 KB Output is correct
2 Correct 2 ms 1620 KB Output is correct
3 Correct 2 ms 1492 KB Output is correct
4 Correct 3 ms 1492 KB Output is correct
5 Correct 5 ms 1676 KB Output is correct
6 Correct 4 ms 1672 KB Output is correct
7 Correct 4 ms 1620 KB Output is correct
8 Correct 3 ms 1632 KB Output is correct
9 Correct 4 ms 1620 KB Output is correct
10 Correct 10 ms 1108 KB Output is correct
11 Correct 5 ms 980 KB Output is correct
12 Correct 225 ms 14188 KB Output is correct
13 Correct 74 ms 12828 KB Output is correct
14 Correct 290 ms 14288 KB Output is correct
15 Correct 304 ms 14104 KB Output is correct
16 Correct 280 ms 14480 KB Output is correct
17 Correct 334 ms 15032 KB Output is correct
18 Correct 306 ms 14736 KB Output is correct
19 Correct 320 ms 16652 KB Output is correct
20 Correct 271 ms 17468 KB Output is correct
21 Correct 338 ms 23476 KB Output is correct