Submission #1080267

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080267		Victor	Ancient Books (IOI17_books)	C++17	0 / 100	2 ms	604 KiB

books

// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#include "books.h"

using namespace std;

#define rep(i, a, b) for (ll i = (a); i < (b); ++i)
#define per(i, a, b) for (ll i = (b) - 1; i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) (ll)x.size()
#define pb push_back
#define debug(x) cout<<#x<<" = "<<x<<endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<ll,pll> ppll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<vll> vvll;

const ll INF = 1'000'000'007;

ll n;

ll encode(vi p,ll pos) {
    ll mul=1;
    ll sum=0;
    rep(i,0,n) {
        sum+=mul*p[i];
        mul*=n+1;
    }
    sum+=pos*mul;
    return sum;
}

pair<vi,ll> decode(ll state) {
    vi vec;
    rep(i,0,n) {
        vec.pb(state%(n+1));
        state/=n+1;
    }
    return {vec,state};
}

long long minimum_walk(std::vector<int> p, int s) {
    n=sz(p);

    ll cycles=0;
    ll ans=0;
    vll vis(n,0);
    rep(i,0,n) {
        if(p[i]==i) continue;

        ans+=abs(i-p[i]);
        if(!vis[i]) ++cycles;

        ll j=i;
        while(!vis[j]) {
            vis[j]=1;
            j=p[j];
        }
    }
    
    ll states=1;
    rep(i,0,n+1) states*=n+1;
    queue<ll> q;
    vll dist(states,INF);
    q.push(encode(p,0));
    dist[encode(p,0)]=0;

    while(!q.empty()) {
        ll state=q.front();
        q.pop();

        vi books;
        ll pos;
        tie(books,pos)=decode(state);

        ll d=dist[state];
        ll holding=-1;
        rep(i,0,n) if(books[i]==n) holding=i;

        if(pos&&dist[encode(books,pos-1)]==INF) {
            dist[encode(books,pos-1)]=d+1;
            q.push(encode(books,pos-1));
        }

        if(pos+1<n&&dist[encode(books,pos+1)]==INF) {
            dist[encode(books,pos+1)]=d+1;
            q.push(encode(books,pos+1));
        }
        
        if(holding==-1) {
            ll book=books[pos];
            books[pos]=n;
            if(dist[encode(books,pos)]==INF) {
                dist[encode(books,pos)]=d;
                q.push(encode(books,pos));
            }
            books[pos]=book;
        }

        if(holding!=-1) {
            ll book=books[pos];
            books[pos]=holding;
            if(dist[encode(books,pos)]==INF) {
                dist[encode(books,pos)]=d;
                q.push(encode(books,pos));
            }
            books[pos]=book;
        }
    }

    vi vec;
    rep(i,0,n) vec.pb(i);
    ll state=encode(vec,0);
    ll ans2=dist[state];


    //cout<<"ans = "<<ans<<" ans2 = "<<ans2<<endl;
    assert(ans==ans2);
    ans+=2*(cycles-1);
    return ans2;
}

/**
#include <cstdio>
#include <vector>
#include <cassert>
// BEGIN SECRET
#include <string>
// END SECRET7

using namespace std;

int main() {
	int n, s;
	assert(2 == scanf("%d %d", &n, &s));

	vector<int> p((unsigned) n);
	for(int i = 0; i < n; i++)
		assert(1 == scanf("%d", &p[(unsigned) i]));

	long long res = minimum_walk(p, s);
	printf("%lld\n", res);
	return 0;
}
/**/

Compilation message (stderr)

books.cpp:161:1: warning: "/*" within comment [-Wcomment]
  161 | /**/
      |

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