Submission #1208093

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208093		jasonic	Ancient Books (IOI17_books)	C++20	0 / 100	0 ms	324 KiB

books

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fastIO cin.tie(0); ios::sync_with_stdio(false)
#define cerr if(0) cout

int n;
ll ans = 0;
int holding = -1;

bool check(vector<int> &a) {
    bool invalid = false;
    for(int i = 0; i < n; i++) {
        if(a[i] == -1) ans |= (holding != i);
        else ans |= (i == a[i]);
    }
    return invalid;
}

void solve(vector<int> &a, int l, int r, bool right = true, bool first = true) {
    cerr << l << ' ' << r << '\n';
    if(l != r) for(int i = right?l:r; (right && i <= r) || (!right && i >= l); right?i++:i--) {
        cerr << i << ' ' << a[i] << '\n';
        if(right) {if((a[i] > holding && a[i] != i && a[i] != 0) || (i == r)) {
            cerr << "swap: " << holding << ' ' << a[i] << '\n';
            swap(holding, a[i]);
        }} else if((a[i] < holding && a[i] != i && a[i] != 0) || (i == l)) {
            cerr << "swap: " << holding << ' ' << a[i] << '\n';
            swap(holding, a[i]);
        }
        if(right && i != r) ans++;
        if(!right && i != l) ans++;
    }
    cerr << holding << '\n';
    for(auto &i : a) cerr << i << ' ';
    cerr << '\n';
    cerr << ans << "\n\n";

    if(l < r && holding != -1 && check(a)) {
        ans++;
        if(right) solve(a, l + first, r-1, false, false);
        else solve(a, l+1 + first, r, true, false);
    } else {
        if(right) ans += r;
        else ans += l;
    }
}

ll minimum_walk(vector<int> p, int s) {
    n = size(p);
    vector<bool> vis(n, false);
    assert(s == 0);
    int l = 0, r = n-1;
    while(p[r] == r && l < r) r--; 

    solve(p, l, r);

    return ans;
}

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