Submission #1080768

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080768		andrei_iorgulescu	Ancient Books (IOI17_books)	C++14	100 / 100	277 ms	238796 KiB

books

#include <bits/stdc++.h>
#include "books.h"
#warning That's not FB, that's my FB

using namespace std;

using ll = long long;

int inf = 1e9;

int n, s;
int p[1000005], pos[1000005];
vector<vector<int>> cyc;
vector<int> cur;
bool viz[1000005];

void dfs(int nod)
{
    viz[nod] = true;
    cur.push_back(nod);
    if (!viz[p[nod]])
        dfs(p[nod]);
}

int vmin[1000005], vmax[1000005];
int rmq_min[21][1000005], rmq_max[21][1000005];
int lg[1000005];

void build()
{
    for (int i = 2; i <= n; i++)
        lg[i] = 1 + lg[i / 2];
    for (int i = 1; i <= n; i++)
    {
        rmq_min[0][i] = vmin[i];
        rmq_max[0][i] = vmax[i];
    }
    for (int j = 1; j <= lg[n]; j++)
    {
        for (int i = 1; i <= n - (1 << j) + 1; i++)
        {
            rmq_min[j][i] = min(rmq_min[j - 1][i], rmq_min[j - 1][i + (1 << (j - 1))]);
            rmq_max[j][i] = max(rmq_max[j - 1][i], rmq_max[j - 1][i + (1 << (j - 1))]);
        }
    }
}

int qmin(int l, int r)
{
    int lgg = lg[r - l + 1];
    return min(rmq_min[lgg][l], rmq_min[lgg][r - (1 << lgg) + 1]);
}

int qmax(int l, int r)
{
    int lgg = lg[r - l + 1];
    return max(rmq_max[lgg][l], rmq_max[lgg][r - (1 << lgg) + 1]);
}

pair<int,int> query(int l, int r)
{
    pair<int,int> uf = {qmin(l,r),qmax(l,r)};
    return uf;
}

pair<int,int> f(pair<int,int> pos)
{
    while (true)
    {
        pair<int,int> repos = query(pos.first,pos.second);
        if (repos.first == pos.first and repos.second == pos.second)
            break;
        pos = repos;
    }
    return pos;
}

int get_cl(pair<int,int> pos)
{
    int cst = 0;
    int inip = pos.second;
    while (pos.second == inip and pos.first != 1)
    {
        cst++;
        pos.first--;
        pos = f(pos);
    }
    if (pos.second == inip)
        return inf;
    return cst;
}

int get_cr(pair<int,int> pos)
{
    int cst = 0;
    int inip = pos.first;
    while (pos.first == inip and pos.second != n)
    {
        cst++;
        pos.second++;
        pos = f(pos);
    }
    if (pos.first == inip)
        return inf;
    return cst;
}

ll minimum_walk(vector<int> PERM, int STR)
{
    cyc.clear();
    memset(viz,0,sizeof(viz));
    n = PERM.size();
    for (int i = 1; i <= n; i++)
        p[i] = PERM[i - 1] + 1, pos[p[i]] = i;
    s = STR + 1;
    for (int i = 1; i <= n; i++)
    {
        if (!viz[i])
        {
            cur.clear();
            dfs(i);
            cyc.push_back(cur);
        }
    }
    for (auto it : cyc)
    {
        sort(it.begin(), it.end());
        for (auto itt : it)
            vmin[itt] = it[0], vmax[itt] = it.back();
    }
    build();
    ll ans = 0;
    for (int i = 1; i <= n; i++)
        ans += abs(i - p[i]);
    int pzz = 1;
    while (pzz < s and p[pzz] == pzz)
        ans -= 2, pzz++;
    pzz = n;
    while (pzz > s and p[pzz] == pzz)
        ans -= 2, pzz--;
    pair<int,int> pos = f({s,s});
    while (pos.first != 1 or pos.second != n)
    {
        int cl = get_cl(pos), cr = get_cr(pos);
        if (cl == inf)
        {
            while (pos.first != 1)
            {
                ans += 2;
                pos.first--;
                pos = f(pos);
            }
            while (pos.second != n)
            {
                ans += 2;
                pos.second++;
                pos = f(pos);
            }
        }
        else
        {
            if (cl <= cr)
            {
                for (int i = 1; i <= cl; i++)
                {
                    ans += 2;
                    pos.first--;
                    pos = f(pos);
                }
            }
            else
            {
                for (int i = 1; i <= cr; i++)
                {
                    ans += 2;
                    pos.second++;
                    pos = f(pos);
                }
            }
        }
    }
    return ans;
}

/**
doamne cate try-uri pana sa ajung la greedy-ul corect
daca faceam asta la cf era atat de over

In fine, eu mereu domin un interval [L R] cu prop ca f(L, R) = (L, R)
f(L, R) = (L, R) daca nu exista vreun i in (L R) care sa faca parte dintr-un ciclu care contine un j inn afara (L R)
Altfel f(L, R) = f(intv reunit cu intervalul ciclului aluia kind of stuff), idk doar un aint de minime si maxime

Acum, din (L, R) tu poti plati 2 bani ca sa faci artificial L-- sau R++
Fie cL = nr minim de mutari pe stanga astfel incat daca le faci, te extinzi pana la urma si in dreapta
cR = nr minim de mutari in dreapta astfel incat pana la urma te extinzi in stanga

Proof penal => e optim sa faci mutari in directia cu costul minim (adica faci min(cL, cR) mutari intr-o directie si vezi unde dai)
Ma rog, daca cL = cR = inf (nu poate fi doar una inf si una nu, ofc), spamezi mutari in ambele parti pana ajungi la capat

In fine, la final scazi 2 * (marimea sufixului de p[i] = i + marimea prefixului de p[i] = i)

Kinda se reduce la a gasi cL si cR eficient... chestia funny e ca nu trebuie vreo structura complicata
Gen, daca doar simulezi, oricum mereu te extinzi cu 1 intr-o parte, deci daca faci O(k) query-uri de aint, se va extinde (L, R) la final O(k)
Deci tot O(NlogN) iese sau cv de genul

Ce boti oamenii ca au bagat asa putini 50 -> 100
**/

Compilation message (stderr)

books.cpp:3:2: warning: #warning That's not FB, that's my FB [-Wcpp]
    3 | #warning That's not FB, that's my FB
      |  ^~~~~~~

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