Submission #151805

#	Time	Username	Problem	Language	Result	Execution time	Memory
151805		qkxwsm	Ancient Books (IOI17_books)	C++14	42 / 100	168 ms	23500 KiB

books

/*
PROG: template
LANG: C++11
    _____
  .'     '.
 /  0   0  \
|     ^     |
|  \     /  |
 \  '---'  /
  '._____.'
 */
#include <bits/stdc++.h>
#include "books.h"

using namespace std;

template<class T>
void readi(T &x)
{
	T input = 0;
	bool negative = false;
	char c = ' ';
	while (c < '-')
	{
		c = getchar();
	}
	if (c == '-')
	{
		negative = true;
		c = getchar();
	}
	while (c >= '0')
	{
		input = input * 10 + (c - '0');
		c = getchar();
	}
	if (negative)
	{
		input = -input;
	}
	x = input;
}
template<class T>
void printi(T output)
{
	if (output == 0)
	{
		putchar('0');
		return;
	}
	if (output < 0)
	{
		putchar('-');
		output = -output;
	}
	int aout[20];
	int ilen = 0;
	while(output)
	{
		aout[ilen] = ((output % 10));
		output /= 10;
		ilen++;
	}
	for (int i = ilen - 1; i >= 0; i--)
	{
		putchar(aout[i] + '0');
	}
	return;
}
template<class T>
void ckmin(T &a, T b)
{
	a = min(a, b);
}
template<class T>
void ckmax(T &a, T b)
{
	a = max(a, b);
}
long long randomize(long long mod)
{
	return ((1ll << 30) * rand() + (1ll << 15) * rand() + rand()) % mod;
}

#define MP make_pair
#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second

const long double PI = 4.0 * atan(1.0);
const long double EPS = 1e-20;

#define MAGIC 347
#define SINF 10007
#define CO 1000007
#define INF 1000000007
#define BIG 1000000931
#define LARGE 1696969696967ll
#define GIANT 2564008813937411ll
#define LLINF 2696969696969696969ll
#define MAXN 1013

long long normalize(long long x, long long mod = INF)
{
	return (((x % mod) + mod) % mod);
}

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int N, S, K;
vector<int> arr;
bool vis[MAXN];
bool useless[MAXN];
vector<int> cyc[MAXN];
int id[MAXN];
int lt[MAXN], rt[MAXN];
ll ans = 0;
bool seen[MAXN][MAXN];
bool ex[MAXN][MAXN];
pii ext[MAXN][MAXN];
int dp[MAXN][MAXN];
int mintable[25][MAXN], maxtable[25][MAXN];
int lg2[MAXN];
vector<int> pts;

int query(int L, int R, bool flag)
{
	//query min
	//floor of log2?
	int SZ = R - L + 1, lg = lg2[SZ];
	if (flag)
	{
		return max(maxtable[lg][L], maxtable[lg][R - (1 << lg) + 1]);
	}
	return min(mintable[lg][L], mintable[lg][R - (1 << lg) + 1]);
}
pii extend(int L, int R)
{
	if (ex[L][R])
	{
		return ext[L][R];
	}
	ex[L][R] = true;
	int lo = L, hi = R;
	while(true)
	{
		int lt = query(lo, hi, 0), rt = query(lo, hi, 1);
		if (lt == lo && rt == hi)
		{
			break;
		}
		ckmin(lo, lt); ckmax(hi, rt);
	}
	ext[L][R] = MP(lo, hi);
	return ext[L][R];
}
int solve(int L, int R)
{
	if (seen[L][R])
	{
		return dp[L][R];
	}
	seen[L][R] = true;
	pii trans;
	if (L == 0)
	{
		if (R == N - 1)
		{
			dp[L][R] = 0;
		}
		else
		{
			trans = extend(L, R + 1);
			dp[L][R] = 2 + solve(trans.fi, trans.se);
		}
	}
	else
	{
		if (R == N - 1)
		{
			trans = extend(L - 1, R);
			dp[L][R] = 2 + solve(trans.fi, trans.se);
		}
		else
		{
			trans = extend(L - 1, R);
			dp[L][R] = 2 + solve(trans.fi, trans.se);
//			if (L == 420 && R == 428) cerr << trans.fi << ' ' << trans.se << ' ' << dp[L][R] << endl;
			trans = extend(L, R + 1);
			ckmin(dp[L][R], 2 + solve(trans.fi, trans.se));
//			if (L == 420 && R == 428) cerr << trans.fi << ' ' << trans.se << ' ' << dp[L][R] << endl;
		}
	}
	//	cerr << L << ' ' << R << ' ' << dp[L][R] << endl;
	return dp[L][R];
}
ll minimum_walk(vector<int> p, int s)
{
	s = p[s];
	for (int j = p.size() - 1; j > s; j--)
	{
		if (p[j] == j)
		{
			useless[j] = true;
		}
		else
		{
			break;
		}
	}
	for (int j = 0; j < s; j++)
	{
		if (p[j] == j)
		{
			useless[j] = true;
		}
		else
		{
			break;
		}
	}
	for (int j = 0; j < p.size(); j++)
	{
		if (!useless[j])
		{
			arr.PB(p[j]);
		}
	}
	if (arr.empty()) return 0;
	N = arr.size();
	int sm = INF;
	for (int i = 0; i < N; i++)
	{
		ckmin(sm, arr[i]);
		if (arr[i] == s)
		{
			S = i;
		}
	}
	//	cerr << S << ' ' << arr[S] << endl;
	for (int i = 0; i < N; i++)
	{
		arr[i] -= sm;
		//		cerr << arr[i] << ' ';
	}
	//	cerr << endl;
	for (int i = 0; i < N; i++)
	{
		if (vis[i])
		{
			continue;
		}
		int u = i;
		do
		{
			vis[u] = true;
			cyc[K].PB(u);
			u = arr[u];
		}
		while(u != i);
		K++;
	}
	for (int i = 0; i < K; i++)
	{
		for (int u : cyc[i])
		{
			id[u] = i;
		}
	}
	for (int i = 0; i < K; i++)
	{
		for (int j = 1; j < cyc[i].size(); j++)
		{
			ans += abs(cyc[i][j] - cyc[i][j - 1]);
		}
		ans += abs(cyc[i].back() - cyc[i][0]);
		lt[i] = INF, rt[i] = -INF;
		for (int u : cyc[i])
		{
			ckmin(lt[i], u);
			ckmax(rt[i], u);
		}
	}
	for (int i = 0; i < N; i++)
	{
		mintable[0][i] = lt[id[i]];
		maxtable[0][i] = rt[id[i]];
		vis[i] = false;
		//		cerr << lt[i] << ' ' << rt[i] << endl;
	}
	for (int i = 0; i <= 20; i++)
	{
		for (int j = (1 << i); j < (2 << i) && j <= N; j++)
		{
			lg2[j] = i;
		}
	}
	for (int i = 1; i <= 20; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (j + (1 << i) - 1 >= N) continue;
			mintable[i][j] = min(mintable[i - 1][j], mintable[i - 1][j + (1 << (i - 1))]);
			maxtable[i][j] = max(maxtable[i - 1][j], maxtable[i - 1][j + (1 << (i - 1))]);
		}
	}
//	cerr << extend(419, 428).fi << ' ' << extend(419, 428).se << endl;
	pii start = extend(S, S);
	solve(start.fi, start.se);
	ans += dp[start.fi][start.se];
	//u -> arr[u]
	//x -> p[x] -> p[p[x]] etc
	//you can swap, at the cost of the difference in pos
	return ans;
}

Compilation message (stderr)

books.cpp: In function 'll minimum_walk(std::vector<int>, int)':
books.cpp:228:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int j = 0; j < p.size(); j++)
                  ~~^~~~~~~~~~
books.cpp:278:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 1; j < cyc[i].size(); j++)
                   ~~^~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 10 / 10
• Subtask 3: 0 / 28
• Subtask 4: 20 / 20
• Subtask 5: 0 / 30