Submission #1028945

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028945		parsadox2	Ancient Books (IOI17_books)	C++17	42 / 100	84 ms	25168 KiB

books

#include "books.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 1e3 + 10;

#define F first
#define S second

int a[N] , n , dp[N][N] , match[N];
bool marked[N] , ch[N];
vector <int> adj[N];

bool try_kuhn(int v)
{
	marked[v] = true;
	for(auto u : adj[v])
	{
		if(match[u] == -1)
		{
			match[u] = v;
			match[v] = u;
			return true;
		}
		if(!marked[match[u]] && try_kuhn(match[u]))
		{
			match[v] = u;
			match[u] = v;
			return true;
		}
	}
	return false;
}

int Matching(int s)
{
	for(int i = 0 ; i < n ; i++)
		match[i] = -1;
	bool flg = true;
	int res = 0;
	while(flg)
	{
		flg = false;
		for(int i = 0 ; i < n ; i++)
			marked[i] = false;
		for(int i = 0 ; i <= s ; i++)  if(match[i] == -1 && try_kuhn(i))
		{
			res++;
			flg = true;
		}
	}
	return res;
}

long long minimum_walk(vector<int> p, int s) {
	n = p.size();
	long long ans = 0;
	int cnt = (p[0] == 0 ? 0 : 1);
	marked[p[0]] = true;
	for(int i = 1 ; i < n ; i++)
	{
		a[i] = cnt;
		ans += 2 * cnt;
		//cout << i << " : " << cnt << endl;
		if(p[i] > i)
		{
			cnt++;
			marked[p[i]] = true;
		}
		if(marked[i])
			cnt--;
	}
	int L = 0 , R = n - 1;
	for(int i = n - 1 ; i > s ; i--)
	{
		if(p[i] != i)
			break;
		R--;	
	}
	for(int i = 0 ; i < s ; i++)
	{
		if(p[i] != i)
			break;
		L++;
	}
	vector <pair<int , int>> all;
	for(int l = L ; l <= s ; l++)   for(int r = s ; r <= R ; r++)
	{
		bool flg = true;
		for(int i = l ; i <= r ; i++)  if(p[i] < l || p[i] > r)
		{
			flg = false;
			break;
		}
		if(!flg)
			continue;
		if(l == L && r == R)
			continue;
		if(l == L)
			ch[r + 1] = true;
		else if(r == R)
			ch[l] = true;
		else
			all.push_back({l , r + 1});
	}
	vector <pair<int , int>> vec;
	for(auto u : all)  if(!ch[u.F] && !ch[u.S])
	{
		adj[u.F].push_back(u.S);
		adj[u.S].push_back(u.F);
	}
	for(int i = 0 ; i < n ; i++)  if(ch[i])
		ans += 2;
	ans += 2 * Matching(s);
	return ans;
}

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