oj.uz

Submission #1093339

# Submission time Handle Problem Language Result Execution time Memory
1093339 2024-09-26T15:24:13 Z 8pete8 Furniture (JOI20_furniture) C++17
100 / 100
 255 ms 59408 KB 
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define int long long
using namespace std;
const int mod=998244353,mxn=2e5+5,inf=1e18,minf=-1e18,lg=30;
//#undef int
int n,k,m,q;
void setIO(string name){		
	ios_base::sync_with_stdio(0); cin.tie(0);		
	freopen((name+".in").c_str(),"r",stdin);		
	freopen((name+".out").c_str(),"w",stdout);	
}
int grid[2002][2002],can[2002][2002],can2[2002][2002],yes[2002][2002];
int cnt[2002],a,b;
//0=l, 1=r
void update(int x,int y){
    if(x==1&&y==1||x==n&&y==m)return;
    if(x<=0||y<=0||x>n||y>m)return;
    if(!yes[x][y])return;
    if((x!=a||y!=b)&&((yes[x-1][y]||yes[x][y-1])&&(yes[x+1][y]||yes[x][y+1])))return;
    yes[x][y]=0;
    cnt[x+y]--;
    update(x-1,y);
    update(x,y-1);
    update(x+1,y);
    update(x,y+1);
}
int32_t main(){
    fastio
	cin>>n>>m;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>grid[i][j];
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
        if(i==1&&j==1)can[i][j]=1;
        if(grid[i][j])continue;
        can[i][j]|=(can[i-1][j]|can[i][j-1]);
    }
    for(int i=n;i>=1;i--)for(int j=m;j>=1;j--){
        if(i==n&&j==m)can2[i][j]=1;
        if(grid[i][j])continue;
        can2[i][j]|=(can2[i+1][j]|can2[i][j+1]);
    }
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
        yes[i][j]=(can[i][j]&can2[i][j]);
        if(yes[i][j])cnt[i+j]++;
    }
    int q;cin>>q;
    while(q--){
        int x,y;cin>>x>>y;
        if(!yes[x][y]){
            grid[x][y]=1;
            cout<<1<<'\n';
        }
        else{
            if(cnt[x+y]>1){
                cout<<1<<'\n';
                grid[x][y]=1;
                a=x,b=y;
                update(x,y);
            }
            else cout<<0<<'\n';
        }
    }
}
/*
*/

Compilation message

furniture.cpp:32:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   32 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
furniture.cpp:38:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   38 | void setIO(string name){
      |                       ^
furniture.cpp:46:24: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   46 | void update(int x,int y){
      |                        ^
furniture.cpp: In function 'void update(long long int, long long int)':
furniture.cpp:47:12: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   47 |     if(x==1&&y==1||x==n&&y==m)return;
      |        ~~~~^~~~~~
furniture.cpp: At global scope:
furniture.cpp:58:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   58 | int32_t main(){
      |              ^
furniture.cpp: In function 'void setIO(std::string)':
furniture.cpp:40:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
furniture.cpp:41:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1628 KB Output is correct
2 Correct 1 ms 2228 KB Output is correct
3 Correct 2 ms 2140 KB Output is correct
4 Correct 2 ms 2344 KB Output is correct
5 Correct 3 ms 2392 KB Output is correct
6 Correct 3 ms 2396 KB Output is correct
7 Correct 3 ms 2392 KB Output is correct
8 Correct 3 ms 2396 KB Output is correct
9 Correct 3 ms 2396 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1628 KB Output is correct
2 Correct 1 ms 2228 KB Output is correct
3 Correct 2 ms 2140 KB Output is correct
4 Correct 2 ms 2344 KB Output is correct
5 Correct 3 ms 2392 KB Output is correct
6 Correct 3 ms 2396 KB Output is correct
7 Correct 3 ms 2392 KB Output is correct
8 Correct 3 ms 2396 KB Output is correct
9 Correct 3 ms 2396 KB Output is correct
10 Correct 6 ms 3416 KB Output is correct
11 Correct 2 ms 1628 KB Output is correct
12 Correct 120 ms 50504 KB Output is correct
13 Correct 55 ms 44800 KB Output is correct
14 Correct 255 ms 52816 KB Output is correct
15 Correct 196 ms 51548 KB Output is correct
16 Correct 204 ms 54940 KB Output is correct
17 Correct 223 ms 57796 KB Output is correct
18 Correct 230 ms 56400 KB Output is correct
19 Correct 226 ms 59408 KB Output is correct
20 Correct 205 ms 59308 KB Output is correct
21 Correct 228 ms 59404 KB Output is correct