Submission #354541

#	Time	Username	Problem	Language	Result	Execution time	Memory
354541		talant117408	Ancient Books (IOI17_books)	C++17	0 / 100	1 ms	364 KiB

books

#include "books.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) int((v).size())
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define OK cout << "OK" << endl;

const int N = 1e6+7;
int belong[N], saizu[N], used[N];
ll dist[N];

ll minimum_walk(vector<int> p, int s){
    if(s) return 0;
    
    vector <ll> pos;
    int num = 0;
    ll ans = 0;
    
    for(int i = 0; i < sz(p); i++){
        if(!used[p[i]]){
            int tmp = p[i];
            while(!used[tmp]){
                dist[num] += abs(tmp-p[tmp]);
                belong[tmp] = num;
                saizu[num]++;
                used[tmp] = 1;
                tmp = p[tmp];
            }
            if(saizu[num] > 1) pos.pb(i);
            num++;
        }
    }
    
    for(int i = 0; i < sz(pos); i++){
        if(!i){
            ans += pos[i];
        }
        else{
            ans += pos[i]-pos[i-1];
        }
        ans += dist[belong[p[pos[i]]]];
    }
    if(sz(pos)){
        ans += pos.back();
    }
    
	return ans;
}

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