oj.uz

Submission #343491

# Submission time Handle Problem Language Result Execution time Memory
343491 2021-01-04T02:09:23 Z Gajowy Climbers (RMI18_climbers) C++14
65 / 100
 800 ms 429676 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 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

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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 3 ms 1900 KB Output is correct
3 Correct 26 ms 18028 KB Output is correct
4 Correct 158 ms 157804 KB Output is correct
5 Correct 448 ms 429036 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 ms 748 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 9 ms 3200 KB Output is correct

Subtask #3
15.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 6 ms 1900 KB Output is correct
3 Correct 226 ms 18004 KB Output is correct
4 Execution timed out 1082 ms 150868 KB Time limit exceeded
5 Execution timed out 969 ms 158060 KB Time limit exceeded
6 Execution timed out 1066 ms 275408 KB Time limit exceeded
7 Execution timed out 973 ms 274252 KB Time limit exceeded
8 Execution timed out 1120 ms 429676 KB Time limit exceeded
9 Execution timed out 1110 ms 424736 KB Time limit exceeded
10 Execution timed out 1116 ms 429576 KB Time limit exceeded