Submission #286295

#	Time	Username	Problem	Language	Result	Execution time	Memory
286295		Mercenary	Ancient Books (IOI17_books)	C++14	50 / 100	260 ms	22776 KiB

books

#ifndef LOCAL
#include "books.h"
#endif

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;

int n;

long long minimum_walk(std::vector<int> p, int s) {
    n = p.size();
    int cur = 0;
    ll res = 0;
    vector<int> vis(n , -1);
    vector<int> mx(n , -1);
    for(int i = 0 ; i < n ; ++i){
        if(vis[i] != -1 || p[i] == i)continue;
        int j = i;
        while(true){
            vis[j] = i;
            mx[i] = max(mx[i] , j);
            if(p[j] == i)break;
            j = p[j];
        }
    }
    int tmp = 0;
    for(int i = 0 ; i < n ; ++i){
        if(vis[i] == i){
            if(tmp < i)res += 2 * (i - tmp);
            tmp = max(tmp , mx[i]);
        }
        res += abs(i - p[i]);
    }
    return res;
}

#ifdef LOCAL
#include "books.h"

#include <cstdio>
#include <vector>
#include <cassert>

using namespace std;

int main() {
    freopen(taskname".INP","r",stdin);
	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;
}

#endif // LOCAL

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:28:9: warning: unused variable 'cur' [-Wunused-variable]
   28 |     int cur = 0;
      |         ^~~

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