Submission #1080350

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080350		Victor	Ancient Books (IOI17_books)	C++17	50 / 100	107 ms	30804 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;

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

    ll cycles=0;
    ll ans=0;
    vll vis(n,0);
    vll mxvals(n,-1);

    rep(i,0,n) {
        if(p[i]==i) continue;

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

        ll j=i;
        ll mx=j;
        while(!vis[j]) {
            vis[j]=1;
            j=p[j];
            mx=max(mx,j);
        }

        mxvals[i]=mx;
    }

    ll mx=0;
    //cout<<ans<<endl;
    rep(i,0,n) {
        //cout<<"i = "<<i<<" mxvals = "<<mxvals[i]<<endl;
        if(mxvals[i]!=-1) {
            //cout<<"i = "<<i<<" mx = "<<mx<<endl;
            if(i) ans+=2*max(0LL,i-mx);
            //cout<<123<<endl;
            mx=max(mx,mxvals[i]);
        }
    }
    

    //cout<<ans<<endl;
    //cout<<cycles<<endl;


    return ans;
}

/**
#include <cstdio>
#include <vector>
#include <cassert>
// BEGIN SECRET
#include <string>
// END SECRET7
x   
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:106:1: warning: "/*" within comment [-Wcomment]
  106 | /**/
      |

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