Submission #1195884

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195884		developinpop	Portals (BOI14_portals)	C++17	0 / 100	0 ms	328 KiB

portals

/*
_____________________.
|____________________|   $$\                                                            $$\           $$\        $$\               
|____________________|   $$ |                                                           \__|          $$ |       $$ |              
|____________________| $$$$$$\    $$$$$$\  $$$$$$\  $$$$$$$\   $$$$$$$\        $$$$$$\  $$\  $$$$$$\  $$$$$$$\ $$$$$$\    $$$$$$$\ 
|____________________| \_$$  _|  $$  __$$\ \____$$\ $$  __$$\ $$  _____|      $$  __$$\ $$ |$$  __$$\ $$  __$$\\_$$  _|  $$  _____|
|____________________|   $$ |    $$ |  \__|$$$$$$$ |$$ |  $$ |\$$$$$$\        $$ |  \__|$$ |$$ /  $$ |$$ |  $$ | $$ |    \$$$$$$\  
                         $$ |$$\ $$ |     $$  __$$ |$$ |  $$ | \____$$\       $$ |      $$ |$$ |  $$ |$$ |  $$ | $$ |$$\  \____$$\ 
                         \$$$$  |$$ |     \$$$$$$$ |$$ |  $$ |$$$$$$$  |      $$ |      $$ |\$$$$$$$ |$$ |  $$ | \$$$$  |$$$$$$$  |
            へ   ♡        \____/ \__|      \_______|\__|  \__|\_______/       \__|      \__| \____$$ |\__|  \__|  \____/ \_______/ 
         ૮ - ՛)                                                                             $$\   $$ |    
         / ⁻ ៸|                                                                              \$$$$$$  |   are human rights :3
     乀 (ˍ,ل ل                       													     \______/ 

*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, 
                         tree_order_statistics_node_update>;
template <typename T>
using ordered_multiset = tree<pair<T, long long>, null_type, 
                      less<pair<T, long long>>, rb_tree_tag, 
                         tree_order_statistics_node_update>;

#define ll long long
#define ld long double
#define inf (ll)1e18
#define pb push_back
#define se second
#define fi first
#define endl '\n'
#define mp make_pair
#define pll pair<ll,ll>
#define kth_smallest find_by_order
#define num_of_smaller order_of_key
#define fori(x) for(ll i=0;i<x;i++)
#define forj(y) for(ll j=0;j<y;j++)

//#define DEBUG

#ifdef DEBUG
#define show(x) cerr<<#x<<" is "<<x<<endl;
#define show2(x,y) cerr<<#x<<" is "<<x<<" "<<#y<<" is "<<y<<endl;
#define show3(x,y,z) cerr<<#x<<" is "<<x<<" "<<#y<<" is "<<y<<" "<<#z<<" is "<<z<<endl;
#define show4(x,y,z,a) cerr<<#x<<" is "<<x<<" "<<#y<<" is "<<y<<" "<<#z<<" is "<<z<<" "<<#a<<" is "<<a<<endl;
#define show_vec(a) for(auto &i:a)cerr<<i<<" ";cerr<<endl;
#define skillissue cerr<<"your code is running\n";
#define getchar_unlocked _getchar_nolock // comment before submission
#else
#define show(x)
#define show2(x,y)
#define show3(x,y,z)
#define show4(x,y,z,a)
#define show_vec(a)
#define skillissue
#endif

/*

inline int readint() {
    int x=0; char ch=getchar_unlocked(); bool s=1;
    while(ch<'0'||ch>'9'){if(ch=='-')s=0;ch=getchar_unlocked();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar_unlocked();}
    return s?x:-x;
}

*/

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll n,m;cin>>n>>m;
	pll to[n][m],bo[n][m],le[n][m],ri[n][m];
	char map[n][m];
	queue<pll> cur;
	pll en;
	fori(n){
		forj(m){
			cin>>map[i][j];
			if(map[i][j]=='S')cur.push(mp(i,j));
			else if(map[i][j]=='C')en=mp(i,j);
		}
	}
	fori(n){
		ll las=0;
		forj(m){
			if(map[i][j]=='#')las=j+1;
			to[i][j]=mp(i,las);
		}
	}
	fori(n){
		ll las=m-1;
		for(ll j=m-1;j>=0;j--){
			if(map[i][j]=='#')las=j-1;
			bo[i][j]=mp(i,las);
		}
	}
	fori(m){
		ll las=0;
		forj(n){
			if(map[j][i]=='#')las=j+1;
			le[j][i]=mp(las,i);
		}
	}
	fori(m){
		ll las=n-1;
		for(ll j=n-1;j>=0;j--){
			if(map[j][i]=='#')las=j-1;
			ri[j][i]=mp(las,i);
		}
	}
	/*
	fori(n){
		forj(m){
			cerr<<to[i][j].fi<<','<<to[i][j].se<<" ";
		}cerr<<endl;
	}
	*/
	ll cnt=0;
	queue<pll> temp,emp;
	map[cur.front().fi][cur.front().se]='#';
	while(cur.size()){
		show(cur.size())
		while(cur.size()){
			if(cur.front()==en){
				cout<<cnt;
				return 0;
			}
			ll x=cur.front().fi,y=cur.front().se;cur.pop();
			show2(x,y);
			for(ll i=-1;i<=1;i++){
				for(ll j=-1;j<=-1;j++){
					if((abs(i)==1 and j==0)or(abs(j)==1 and i==0)){
						ll X=x+i,Y=y+j;
						if(X<n and X>=0 and Y<m and Y>=0 and map[X][Y]!='#'){
							map[X][Y]='#';
							temp.push(mp(X,Y));
						}
					}
				}
			}
			pll things[4];things[0]=to[x][y];things[1]=bo[x][y];things[2]=le[x][y];things[3]=ri[x][y];
			for(auto k:things){
				ll X=k.fi,Y=k.se;
				if(X<n and X>=0 and Y<m and Y>=0 and map[X][Y]!='#'){
					map[X][Y]='#';
					temp.push(mp(X,Y));
				}
			}
		}
		cnt++;
		cur=temp;
		temp=emp;
	}
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30