oj.uz

Submission #343454

# Submission time Handle Problem Language Result Execution time Memory
343454 2021-01-04T00:12:31 Z Gajowy Climbers (RMI18_climbers) C++14
65 / 100
 800 ms 392620 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++)
			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]),pq.push({d[(n*j+i)*2+wh],(n*j+i)*2+wh});
							//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]),pq.push({d[(n*j+i)*2+wh],(n*j+i)*2+wh});
					}
				}
}

int32_t main(){
	fastio;
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>a[i];
	fill(d,d+n*n*2+1,inf);
	for(int i=0;i<n;i++)
		pq.push({0,(n*i+i)*2}),d[(n*i+i)*2]=0;
	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=pq.front().e1;
		int who=pq.front().e2&1;
		int u=((pq.front().e2)/2)%n,v=((pq.front().e2)/2)/n;
		//cout<<u<<' '<<v<<' '<<who<<'\n';
		pq.pop();
		extend(u,v,who,dist);
	}
	if(d[(n*n-n)*2]==inf&&d[(n*n-n)*2+1]==inf)
		cout<<"NO\n";
	else
		cout<<min(d[(n*n-n)*2],d[(n*n-n)*2+1])<<'\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 5 ms 1772 KB Output is correct
3 Correct 36 ms 16108 KB Output is correct
4 Correct 199 ms 141548 KB Output is correct
5 Correct 583 ms 392444 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 3 ms 748 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 10 ms 2924 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 12 ms 1772 KB Output is correct
3 Correct 417 ms 16220 KB Output is correct
4 Execution timed out 1110 ms 141696 KB Time limit exceeded
5 Execution timed out 1072 ms 141676 KB Time limit exceeded
6 Execution timed out 1082 ms 251500 KB Time limit exceeded
7 Execution timed out 1064 ms 251628 KB Time limit exceeded
8 Execution timed out 1099 ms 392620 KB Time limit exceeded
9 Execution timed out 1116 ms 392556 KB Time limit exceeded
10 Execution timed out 1122 ms 392556 KB Time limit exceeded