Submission #343491

#	Time	Username	Problem	Language	Result	Execution time	Memory
343491		Gajowy	Climbers (RMI18_climbers)	C++14	65 / 100	1120 ms	429676 KiB

climbers

#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 size(x) (int)x.size()
#define all(r) begin(r),end(r)
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define time chrono::high_resolution_clock().now().time_since_epoch().count()
#define satori int testCases; cin>>testCases; while(testCases--)

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

///////////////////
#define DEBUG if(1)
///////////////////

const int MAXN=5e3+10;
const ll inf=1e18+2137;

bool used[MAXN*MAXN*2];
ll d[MAXN*MAXN*2];
int a[MAXN],n;
//priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
queue<pair<ll,int>> pq;
bool cango(int pos,int lvl,int pos2,int lvl2){
	if(lvl2<a[pos2]){
		if(pos2==0)
			return false;
		if(a[pos2-1]>lvl2)
			return false;
		if(abs(pos-pos2)>1)
			return false;
		if(pos==pos2)
			return true;
		if(pos==pos2-1&&lvl>a[pos])
			return false;
		if(pos==pos2+1&&lvl<a[pos2])
			return false;
		return true;
	}
	else
	if(lvl2>a[pos2]){
		if(pos2==0)
			return false;
		if(a[pos2-1]<lvl2)
			return false;
		if(abs(pos-pos2)>1)
			return false;
		if(pos==pos2)
			return true;
		if(pos==pos2-1&&lvl<a[pos])
			return false;
		if(pos==pos2+1&&lvl>a[pos2])
			return false;
		return true;
	}
	else{
		if(abs(pos-pos2)>1)
			return false;
		if(pos==pos2)
			return true;
		if(pos2+1==pos)
			return true;
		if(pos2-1==pos){
			if(a[pos2-1]==a[pos2]){
				if(lvl!=lvl2)
					return false;
				return true;
			}
			else
			if(a[pos2-1]>a[pos2]){
				if(lvl>=a[pos2-1])
					return true;
				return false;
			}
			else{
				if(lvl<=a[pos2-1])
					return true;
				return false;
			}
		}
		return true;
	}
	return false;
}

void extend(int l,int r,int who,ll dist){
	int lvl=(who==0?a[l]:a[r]);
	for(int i=max(0,l-1);i<=min(n-1,l+1);i++)
		for(int j=max(0,r-1);j<=min(n-1,r+1);j++){
			if(i>j)
				continue;
			for(int wh=0;wh<2;wh++)
				if(wh==0){
					if(cango(l,lvl,i,a[i])&&cango(r,lvl,j,a[i])){
						//if(l==r&&l==3&&i==2&&j==4&&wh==0)
							//cout<<"Xd"<<' '<<d[(n*r+l)*2+who]<<' '<<abs(lvl-a[i])<<' '<<d[(n*j+i)*2+wh]<<'\n';
						if(d[(n*r+l)*2+who]+abs(lvl-a[i])<d[(n*j+i)*2+wh]){
							d[(n*j+i)*2+wh]=d[(n*r+l)*2+who]+abs(lvl-a[i]);
							if(!used[(n*j+i)*2+wh]){
								pq.push({d[(n*j+i)*2+wh],(n*j+i)*2+wh});
								used[(n*j+i)*2+wh]=true;
							}
							//if(l==r&&l==3&&i==2&&j==4&&wh==0)
							//cout<<"Xd";

						}
					}
				}
				else{
					if(cango(l,lvl,i,a[j])&&cango(r,lvl,j,a[j])){
						if(d[(n*r+l)*2+who]+abs(lvl-a[j])<d[(n*j+i)*2+wh]){
							d[(n*j+i)*2+wh]=d[(n*r+l)*2+who]+abs(lvl-a[j]);
							if(!used[(n*j+i)*2+wh]){
								pq.push({d[(n*j+i)*2+wh],(n*j+i)*2+wh});
								used[(n*j+i)*2+wh]=true;
							}
						}
					}
				}
		}
}

int32_t main(){
	fastio;
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>a[i];
	fill(d,d+n*n*2+1,inf);
	pq.push({0,(n*n-n)*2}),d[(n*n-n)*2]=0,used[(n*n-n)*2]=true;
	pq.push({0,(n*n-n)*2+1}),d[(n*n-n)*2+1]=0,used[(n*n-n)*2+1]=true;
	while(size(pq)){
		//if(pq.top().e2==(n*n-n)*2||pq.top().e2==(n*n-n)*2+1)
			//break;
		/*if(used[pq.top().e2]){
			pq.pop();
			continue;
		}
		else
			used[pq.top().e2]=true;*/
		ll dist=d[pq.front().e2];
		int who=pq.front().e2&1;
		int u=((pq.front().e2)/2)%n,v=((pq.front().e2)/2)/n;
		//cout<<u<<' '<<v<<' '<<who<<'\n';
		used[pq.front().e2]=false;
		pq.pop();
		extend(u,v,who,dist);
	}
	ll ans=inf;
	for(int i=0;i<n;i++)
		ans=min({ans,d[(n*i+i)*2],d[(n*i+i)*2+1]});
	if(ans==inf)
		cout<<"NO\n";
	else
		cout<<ans<<'\n';
	//3 3 0 -> 2 4 0
	//cout<<cango(3,7,2,2)<<'\n';
	//cout<<cango(3,7,4,2)<<'\n';
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 15 / 50