Submission #1331777

#TimeUsernameProblemLanguageResultExecution timeMemory
1331777secondaccountmaybeJetpack (COCI16_jetpack)C++20
0 / 80
144 ms131072 KiB
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n;
	cin>>n;
	vector<string>g(10);
	for(ll i=0;i<10;i++)
	{
		cin>>g[i];
	}
	vector<vector<vector<bool>>>v(n,vector<vector<bool>>(10,vector<bool>(2,false)));
	struct s
	{
		ll c,r,j;
	};
	struct p
	{
		ll r,j;
	};
	vector<vector<vector<p>>>h(n,vector<vector<p>>(10,vector<p>(2,{-1,-1})));
	queue<s> q;
	if(g[9][0]=='.')
	{
		v[0][9][0]=true;
		q.push({0,9,0});
		v[0][9][1]=true;
		q.push({0,9,1});
	}
	bool f=false;
	ll r1=-1,j1=-1;
	while(!q.empty())
	{
		s t=q.front();
		q.pop();
		if(t.c==n-1)
		{
			f=true;
			r1=t.r;
			j1=t.j;
			break;
		}
		for(ll j2:{0LL,1LL})
		{
			ll r2=t.r;
			if(j2==1)
			{
				r2=max(0LL,t.r-1);
			}
			else
			{
				r2=min(9LL,t.r+1);
			}
			if(g[r2][t.c+1]!='X'&&!v[t.c+1][r2][j2])
			{
				v[t.c+1][r2][j2]=true;
				h[t.c+1][r2][j2]={t.r,t.j};
				q.push({t.c+1,r2,j2});
			}
		}
	}
	if(!f)
	{
		cout<<0<<endl;
	}
	else
	{
		vector<p> a;
		ll c2=n-1,r2=r1,j2=j1;
		while(c2>=0)
		{
			a.push_back({r2,j2});
			p b=h[c2][r2][j2];
			r2=b.r;
			j2=b.j;
			c2--;
		}
		reverse(a.begin(),a.end());
		vector<pair<ll,ll>>m;
		ll i=0;
		while(i<n)
		{
			if(a[i].j==1)
			{
				ll s1=i;
				while(i<n&&a[i].j==1)
				{
					i++;
				}
				m.push_back({s1,i-s1});
			}
			else
			{
				i++;
			}
		}
		cout<<m.size()<<endl;
		for(auto k:m)
		{
			cout<<k.first<<" "<<k.second<<endl;
		}
	}
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...