Submission #428408

#	Time	Username	Problem	Language	Result	Execution time	Memory
428408		jeqcho	Ancient Books (IOI17_books)	C++17	12 / 100	2065 ms	292 KiB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define F0R(i,b) FOR(i,0,b)
#define ROF(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define R0F(i,b) ROF(i,0,b)
#define all(x) begin(x),end(x)
#define pb push_back
#define trav(a,x) for(auto&a:x)
#define sz(x) int(x.size())

vi p;
int n;
ll ans=1e18;

bool ok(int now)
{
	if(now!=0)return 0;
	F0R(i,n)
	{
		if(p[i]!=i)return 0;
	}
	return 1;
}
	

void go(int now,int cur,ll d,int cnt)
{
	if(now<0||now>=n)return;
	if(cnt>6)return;
	if(ok(now))
	{
		ans=min(ans,d);
		return;
	}
	FOR(i,-n,n)
	{
		go(now+i,cur,d+abs(i),cnt+1);
	}
	swap(cur,p[now]);
	FOR(i,-n,n)
	{
		go(now+i,cur,d+abs(i),cnt+1);
	}
	swap(cur,p[now]);
}

ll minimum_walk(vi p1, int s) {
	n=sz(p1);
	p=p1;
	go(0,-1,0,0);
	return ans;
}

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