oj.uz

답안 #47233

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
47233 2018-04-29T12:00:08 Z PowerOfNinjaGo 고대 책들 (IOI17_books) C++17
0 / 100
 15 ms 760 KB 
//Power Of Ninja Go
#include <bits/stdc++.h>
#ifdef atom
	#include "grader.cpp"
#else
	#include "books.h"
#endif
using namespace std;
typedef long long ll; typedef pair<int, int> ii; typedef vector<int> vi; typedef vector< ii > vii;
#define X first
#define Y second
#define pb push_back
int n;
const int maxn = 1e6+5;
vector<int> p;
int a[maxn], b[maxn];
ll dist[maxn];
bool vis[maxn];
int belong[maxn];
int cnt = 0;
void dfs(int u)
{
	if(vis[u]) return;
	vis[u] = true;
	belong[u] = cnt;
	a[cnt] = min(u, a[cnt]);
	b[cnt] = max(u, b[cnt]);
	dist[cnt] += abs(p[u]-u);
	dfs(p[u]);
}
void change(int &l, int &r)
{
	int ll = min(l, min(a[belong[l]], a[belong[r]]));
	int rr = max(r, max(b[belong[l]], b[belong[r]]));
	while(ll< l || r< rr)
	{
		if(ll< l)
		{
			l--;
			ll = min(ll, a[belong[l]]);
			rr = max(rr, b[belong[l]]);
		}
		else
		{
			r++;
			ll = min(ll, a[belong[r]]);
			rr = max(rr, b[belong[r]]);
		}
	}
}
int solve(int l, int r, int want_l, int want_r)
{
	int ret = 0;
	do
	{
		change(l, r);
		//cout << l << ' ' << r << endl;
		bool to_left = false;
		int costL = 0;
		int s_l = l, s_r = r;
		while(true)
		{
			if(s_l<= want_l) break;
			s_l--;
			costL += 2;
			change(s_l, s_r);
			if(s_r> r)
			{
				to_left = true;
				break;
			}
		}
		//cout << s_l << '?' << s_r << endl;
		bool to_right = false;
		int costR = 0;
		int k_l = l, k_r = r;
		while(true)
		{
			if(s_r>= want_r) break;
			k_r++;
			costR += 2;
			change(k_l, k_r);
			if(k_l< l)
			{
				to_right = true;
				break;
			}
		}
		if(to_left && to_right)
		{
			ret += min(costL, costR);
		}
		else
		{
			ret += costL + costR;
		}
		l = min(s_l, k_l);
		r = max(s_r, k_r);
	}
	while(want_l< l || r< want_r);
	return ret;
}
long long minimum_walk(std::vector<int> P, int s)
{
	p = P;
	n = P.size();
	for(int i = 0; i< n; i++) a[i] = 1e9;
	int l = s, r = s;
	ll res = 0;
	for(int i = 0; i< n; i++)
	{
		if(vis[i]) continue;
		dfs(i);
		res += dist[cnt];
		if(a[cnt] != b[cnt])
		{
			l = min(l, a[cnt]);
			r = max(r, b[cnt]);
		}
		cnt++;
	}
	//don't forget when s = 0
	return res+solve(s, s, l, r);
}

Subtask #1
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 15 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 15 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 15 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 688 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Incorrect 2 ms 760 KB 3rd lines differ - on the 1st token, expected: '2094', found: '2110'
5 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 15 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -