Submission #292782

#	Time	Username	Problem	Language	Result	Execution time	Memory
292782		shayan_p	Ancient Books (IOI17_books)	C++17	22 / 100	2070 ms	12024 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);
    assert(s == 0);
    memset(cnt, 0, sizeof cnt);
    ll ans = 0;
    while(n > 1 && p[n-1] == n-1)
	n--, p.pop_back();
    for(int i = 0; i < n; i++){
	int l = i, r = p[i];
	if(l > r)
	    swap(l, r);
	ans+= r-l;
	while(l < r)
	    cnt[l] = 1, l++;
    }
    /*
    int sm = 0;
    for(int i = 0; i < n-1; i++){
	sm+= cnt[i];
	ans+= (sm > 0 ? 0 : 2);
	}*/
    for(int i = 0; i < n-1; i++){
	ans+= cnt[i] == 0 ? 2 : 0;
    }
    return ans;
}

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