Submission #616160

#	Time	Username	Problem	Language	Result	Execution time	Memory
616160		rrrr10000	Ancient Books (IOI17_books)	C++14	42 / 100	2080 ms	16344 KiB

books

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<bool> vb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define fi first
#define se second
#define lb(v,k) (lower_bound(all(v),k)-v.bein())
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
#define pb emplace_back
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<endl;}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
const ll inf=1001001001001001001;
long long minimum_walk1(std::vector<int> p, int s) {
	ll l=0,r=p.size()-1;
	while(l<s&&p[l]==l)l++;
	while(r>s&&p[r]==r)r--;
	vi v;
	REP(i,l,r+1)v.pb(p[i]-l);
	s-=l;
	ll n=v.size(),ans=0;
	rep(i,n-1){
		ll c=0;
		rep(j,i+1)if(v[j]>i)c++;
		if(c==0)c++;
		ans+=c;
	}
	return ans*2;
}
long long minimum_walk(std::vector<int> p, int s) {
	ll l=0,r=p.size()-1;
	while(l<s&&p[l]==l)l++;
	while(r>s&&p[r]==r)r--;
	vi v;
	REP(i,l,r+1)v.pb(p[i]-l);
	s-=l;
	ll n=v.size(),ans=0;
	rep(i,n-1){
		rep(j,i+1)if(v[j]>i)ans++;
	}
	vvi dp(n,vi(n,inf));
	dp[s][s]=0;
	for(ll l=s;l>=0;l--){
		ll mi=inf,ma=-inf;
		REP(r,l,n){
			chmax(ma,v[r]);
			chmin(mi,v[r]);
			if(l)chmin(dp[l-1][r],dp[l][r]+1);
			if(r!=n-1)chmin(dp[l][r+1],dp[l][r]+1);
			chmin(dp[min(l,mi)][max(r,ma)],dp[l][r]);
		}
	}
	return (ans+dp[0][n-1])*2;
}
void check(ll n,ll s){
	map<vi,ll> dp;
	vi tmp(n+1);rep(i,n)tmp[i]=i;
	tmp[n]=n;
	tmp.pb(s);
	dp[tmp]=0;
	deque<vi> deq;
	deq.pb(tmp);
	ll cnt=0;
	while(!deq.empty()){
		auto t=deq.front();deq.pop_front();
		vi nex=t;
		swap(nex[n],nex[nex.back()]);
		if(!dp.count(nex)){
			dp[nex]=dp[t];deq.push_front(nex);
		}
		nex=t;
		if(nex.back()!=n-1)nex.back()++;
		if(!dp.count(nex)){
			dp[nex]=dp[t]+1;deq.pb(nex);
		}
		nex=t;
		if(nex.back()!=0)nex.back()--;
		if(!dp.count(nex)){
			dp[nex]=dp[t]+1;deq.pb(nex);
		}
	}
	for(auto x:dp)if(x.fi[n+1]==s&&x.fi[n]==n){
		vector<int> p;
		rep(i,n)p.pb(x.fi[i]);
		if(minimum_walk(p,s)!=x.se){
			outv(p);
			out(s);
			out(minimum_walk(p,s));
			out(x.se);
			return;
		}
	}
}
/*
int main(){
	rep(tt,100000){
		ll n=rand()%7+1;
		out(n);
		vector<int> p(n);rep(i,n)p[i]=i;
		random_shuffle(all(p));
		ll r1=minimum_walk_g(p,0);
		ll r2=minimum_walk(p,0);
		if(r1!=r2){
			out(tt);
			outv(p);
			out(r1);out(r2);
			break;
		}
	}
	// REP(n,1,9)rep(s,n)check(n,s);
}
*/

Compilation message (stderr)

books.cpp: In function 'void check(ll, ll)':
books.cpp:72:5: warning: unused variable 'cnt' [-Wunused-variable]
   72 |  ll cnt=0;
      |     ^~~

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