oj.uz

Submission #343449

# Submission time Handle Problem Language Result Execution time Memory
343449 2021-01-03T23:59:36 Z Gajowy Climbers (RMI18_climbers) C++14
65 / 100
 800 ms 439664 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;

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.top().e1;
		int who=pq.top().e2&1;
		int u=((pq.top().e2)/2)%n,v=((pq.top().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 2 ms 492 KB Output is correct
2 Correct 6 ms 2028 KB Output is correct
3 Correct 44 ms 18028 KB Output is correct
4 Correct 264 ms 159088 KB Output is correct
5 Correct 718 ms 439664 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 492 KB Output is correct
5 Correct 14 ms 3308 KB Output is correct

Subtask #3
15.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 492 KB Output is correct
2 Correct 13 ms 2028 KB Output is correct
3 Correct 529 ms 18284 KB Output is correct
4 Execution timed out 1049 ms 159092 KB Time limit exceeded
5 Execution timed out 1099 ms 158444 KB Time limit exceeded
6 Execution timed out 1097 ms 274716 KB Time limit exceeded
7 Execution timed out 1097 ms 271212 KB Time limit exceeded
8 Execution timed out 1118 ms 430700 KB Time limit exceeded
9 Execution timed out 1081 ms 417004 KB Time limit exceeded
10 Execution timed out 1109 ms 419816 KB Time limit exceeded