Submission #292827

#	Time	Username	Problem	Language	Result	Execution time	Memory
292827		shayan_p	Ancient Books (IOI17_books)	C++17	50 / 100	194 ms	12224 KiB

books

// Oh damn! Suddenly you're free to fly...
 
#include<bits/stdc++.h>
#include "books.h"
 
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
 
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
 
const int maxn = 1e6 + 10, mod = 1e9 + 7, inf = 1e9 + 10;
 
int cnt[maxn];
 
ll minimum_walk(vector<int> p, int s){
    int n = sz(p);
    ll ans = 0;
    for(int i = 0; i < n; i++){
	int l = i, r = p[i];
	if(l > r)
	    swap(l, r);
	ans+= r-l;
	cnt[l]++, cnt[r]--;
    }
    int sm = 0;
    for(int i = 0; i < n-1; i++){
	sm+= cnt[i];
	ans+= (sm > 0 ? 0 : 2);
    }
    for(int i = 0; i < s && p[i] == i; i++){
	ans-= 2;
    }
    for(int i = n-1; i > s && p[i] == i; i--){
	ans-= 2;
    }
    if(p[s] != s)
	return ans;
    assert(s == 0);
    int L = s, R = s;
    while(L >= 0 && p[L] == L)
	L--;
    while(R < n && p[R] == R)
	R++;
    if(L == -1 || R == n)
	return ans;
    assert(0);
    return ans + 2 * min(s - L, R - s);
}

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