Submission #585791

#	Time	Username	Problem	Language	Result	Execution time	Memory
585791		InternetPerson10	Ancient Books (IOI17_books)	C++17	50 / 100	327 ms	37812 KiB

books

#include "books.h"
#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

vector<ll> rands;
vector<int> dist;
map<ll, int> ma;

long long minimum_walk(vector<int> p, int s) {
    srand(time(NULL));
    int n = p.size();
    rands.resize(n, 0);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < 4; j++) {
            rands[i] *= 32768;
            rands[i] += (rand() % 32768);
        }
    }
    ll tot = 0;
    vector<bool> taken(n, false);
    vector<int> nums(n, -1);
    for(int i = 0; i < n; i++) {
        if(!taken[i]) {
            int x = i;
            int l = i, r = i;
            while(!taken[x]) {
                taken[x] = true;
                tot += abs(x - p[x]);
                x = p[x];
                l = min(l, x);
                r = max(r, x);
            }
            if(l != r) {
                nums[l] = nums[r] = l;
            }
        }
    }
    ll hash = 0;
    int lastZero = 0;
    int lastImpt = -999999;
    bool foundC = false;
    int l1 = s-1, r1 = s;
    for(int i = 0; i < n; i++) {
        if(nums[i] == -1) {
            if(hash == 0) tot += 2;
            continue;
        }
        lastImpt = i;
        hash ^= rands[nums[i]];
        if(hash) {
            if(ma.count(hash)) {
                int l = ma[hash], r = i;
                if(l <= l1 && r1 <= r) {
                    tot += 2 * min(r - r1, l1 - l);
                }
                ma.erase(hash);
            }
            else ma[hash] = i;
        }
        else {
            if(i != lastZero) tot += 2;
            lastZero = i + 1;
        }
    }
    for(int i = 0; i < n; i++) {
        if(p[i] == i && i != s) tot -= 2;
        else break;
    }
    for(int i = n-1; i >= 0; i--) {
        if(p[i] == i && i != s) tot -= 2;
        else break;
    }
    return max(0LL, tot - 2);
}

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:42:9: warning: variable 'lastImpt' set but not used [-Wunused-but-set-variable]
   42 |     int lastImpt = -999999;
      |         ^~~~~~~~
books.cpp:43:10: warning: unused variable 'foundC' [-Wunused-variable]
   43 |     bool foundC = false;
      |          ^~~~~~

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