Submission #1080763

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080763		andrei_iorgulescu	Ancient Books (IOI17_books)	C++14	42 / 100	2079 ms	86396 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];

pair<int,int> query(int ha, int haha, int hahaha, int l, int r)
{
    pair<int,int> uf = {l,r};
    for (int i = l; i <= r; i++)
    {
        uf.first = min(uf.first, vmin[i]);
        uf.second = max(uf.second, vmax[i]);
    }
    return uf;
}

pair<int,int> f(pair<int,int> pos)
{
    while (true)
    {
        pair<int,int> repos = query(1,1,n,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();
    }
    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
**/

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: 0 / 28
• Subtask 4: 20 / 20
• Subtask 5: 0 / 30