oj.uz

Submission #294127

# Submission time Handle Problem Language Result Execution time Memory
294127 2020-09-08T15:45:10 Z Gajowy Furniture (JOI20_furniture) C++14
100 / 100
 372 ms 10704 KB 
#pragma GCC optimize("Ofast")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define e1 first
#define e2 second
#define int int_fast32_t
#define uint uint_fast64_t
#define ll int_fast64_t
#define ull uint_fast64_t
#define int16 int_fast16_t
#define uint16 uint_fast16_t
#define int32 int_fast32_t
#define uint32 uint_fast32_t
#define int64 int_fast64_t
#define uint64 uint_fast64_t
#define ld long double
#define float long double
#define size(x) (int)x.size()
#define satori int testCases; cin>>testCases; while(testCases--)
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define all(r) begin(r),end(r)
#define rall(r) rbegin(r),rend(r)
#define time chrono::high_resolution_clock().now().time_since_epoch().count()
#define elapsed(__begin,__end) (__end-__begin)/CLOCKS_PER_SEC
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
float pi=3.14159265358979323846;

const int MAXN=1e3+10;

bool bad[MAXN][MAXN],hi[MAXN][MAXN],lo[MAXN][MAXN];

void clean_hi(int x,int y)
{
	hi[x][y]=false;
	if(hi[x-1][y])
		clean_hi(x-1,y);
	else
	if(hi[x][y-1])
		clean_hi(x,y-1);
}

bool extend_hi(int x,int y)
{
	if(hi[x][y])
	{
		if(hi[x-1][y])
			clean_hi(x-1,y);
		return true;
	}
	if(!bad[x][y+1]&&extend_hi(x,y+1))
	{
		hi[x][y]=true;
		return true;
	}
	if(!bad[x+1][y]&&extend_hi(x+1,y))
	{
		hi[x][y]=true;
		return true;
	}
	bad[x][y]=true;
	return false;
}

void clean_lo(int x,int y)
{
	lo[x][y]=false;
	if(lo[x-1][y])
		clean_lo(x-1,y);
	else
	if(lo[x][y-1])
		clean_lo(x,y-1);
}

bool extend_lo(int x,int y)
{
	if(lo[x][y])
	{
		if(lo[x][y-1])
			clean_lo(x,y-1);
		return true;
	}
	if(!bad[x+1][y]&&extend_lo(x+1,y))
	{
		lo[x][y]=true;
		return true;
	}
	if(!bad[x][y+1]&&extend_lo(x,y+1))
	{
		lo[x][y]=true;
		return true;
	}
	bad[x][y]=true;
	return false;
}

int32_t main()
{
	fastio;
	int n,m,x,y,cx,cy,q;
	cin>>n>>m;
	for(int i=0;i<=m+1;i++)
		bad[0][i]=bad[n+1][i]=true;
	for(int i=1;i<=n;i++)
		bad[i][0]=bad[i][m+1]=true;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			cin>>x;
			if(x)
				bad[i][j]=true;
			if((i>1||j>1)&&bad[i-1][j]&&bad[i][j-1])
				bad[i][j]=true;
		}
	lo[n][m]=hi[n][m]=true;
	extend_hi(1,1);
	extend_lo(1,1);
	cin>>q;
	while(q--)
	{
		cin>>x>>y;
		if(lo[x][y]&&hi[x][y])
		{
			cout<<"0\n";
			continue;
		}
		cout<<"1\n";
		bad[x][y]=true;
		if(lo[x][y])
		{
			lo[x][y]=false;
			cx=x,cy=y;
			while(true)
			{
				if(lo[cx-1][cy])
					cx--;
				else
					cy--;
				lo[cx][cy]=false;
				if(extend_lo(cx,cy))
					break;
			}
		}
		if(hi[x][y])
		{
			hi[x][y]=false;
			cx=x,cy=y;
			while(true)
			{
				if(hi[cx-1][cy])
					cx--;
				else
					cy--;
				hi[cx][cy]=false;
				if(extend_hi(cx,cy))
					break;
			}
		}
	}
}

Compilation message

furniture.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
furniture.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 2 ms 640 KB Output is correct
4 Correct 3 ms 768 KB Output is correct
5 Correct 3 ms 768 KB Output is correct
6 Correct 3 ms 768 KB Output is correct
7 Correct 3 ms 768 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 3 ms 768 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 2 ms 640 KB Output is correct
4 Correct 3 ms 768 KB Output is correct
5 Correct 3 ms 768 KB Output is correct
6 Correct 3 ms 768 KB Output is correct
7 Correct 3 ms 768 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 3 ms 768 KB Output is correct
10 Correct 9 ms 896 KB Output is correct
11 Correct 3 ms 640 KB Output is correct
12 Correct 156 ms 8056 KB Output is correct
13 Correct 63 ms 5048 KB Output is correct
14 Correct 268 ms 10104 KB Output is correct
15 Correct 290 ms 10104 KB Output is correct
16 Correct 286 ms 10360 KB Output is correct
17 Correct 317 ms 10616 KB Output is correct
18 Correct 280 ms 10504 KB Output is correct
19 Correct 323 ms 10612 KB Output is correct
20 Correct 262 ms 10616 KB Output is correct
21 Correct 372 ms 10704 KB Output is correct