Submission #81156

#	Time	Username	Problem	Language	Result	Execution time	Memory
81156		KemLove	Ancient Books (IOI17_books)	C++14	0 / 100	45 ms	47388 KiB

books

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

typedef double db;
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, int> pt;
typedef pair<int, ii> iii;
typedef vector<int> vi;

#define FOR(i, l, r) for(int i = l; i <= r; ++i)
#define FORD(i, l, r) for(int i = l; i >= r; --i)
#define REP(i, r) for(int i = 0; i < int(r); ++i)
#define REPD(i, r) for(int i = int(r)-1; i >= 0; --i)
#define fi first
#define se second
#define x first
#define y second
#define sz size
#define endl '\n'
#define debug(x) cout << #x << " = " << x << endl;
#define boost ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define mk make_pair

const int Nmax = 2e6 + 10;
const ll inf = 1e9;
const db _eps = 1e-15;

vi a[Nmax];
int n, s, last, startlast;
ll sum;
bool avail[Nmax];

void visit(int u) {
    last = u;
    avail[u] = true;
    REP(i, a[u].sz()) {
        int v = a[u][i];
        sum += 1LL * abs(v - u);
        if (avail[v] == false) {
            visit(v);
        }
    }
}

ll minimum_walk(vi p, int s) {
    s++; n = p.sz();
    FOR(i, 1, n) {
        a[i].push_back(p[i-1]);
    }
    startlast = s;
    FOR(i, s, n) {
        if (avail[i]) continue;
        sum += abs(i - startlast);
        visit(i);
        startlast = i;
    }
    FORD(i, s - 1, 1) {
        if (avail[i]) continue;
        sum += abs(i - startlast);
        visit(i);
        startlast = i;
    }
    return 1LL * abs(s - startlast) + sum;
}

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