oj.uz

Submission #1080763

# Submission time Handle Problem Language Result Execution time Memory
1080763 2024-08-29T13:49:35 Z andrei_iorgulescu Ancient Books (IOI17_books) C++14
42 / 100
 2000 ms 86396 KB 
#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

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1372 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 1 ms 1372 KB Output is correct
4 Correct 1 ms 1372 KB Output is correct
5 Correct 1 ms 1372 KB Output is correct
6 Correct 1 ms 1372 KB Output is correct
7 Correct 1 ms 1372 KB Output is correct
8 Correct 1 ms 1372 KB Output is correct
9 Correct 1 ms 1372 KB Output is correct
10 Correct 1 ms 1372 KB Output is correct
11 Correct 1 ms 1368 KB Output is correct
12 Correct 1 ms 1368 KB Output is correct
13 Correct 1 ms 1372 KB Output is correct
14 Correct 1 ms 1372 KB Output is correct
15 Correct 1 ms 1372 KB Output is correct
16 Correct 1 ms 1372 KB Output is correct
17 Correct 1 ms 1372 KB Output is correct
18 Correct 1 ms 1372 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1372 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 1 ms 1372 KB Output is correct
4 Correct 1 ms 1372 KB Output is correct
5 Correct 1 ms 1372 KB Output is correct
6 Correct 1 ms 1372 KB Output is correct
7 Correct 1 ms 1372 KB Output is correct
8 Correct 1 ms 1372 KB Output is correct
9 Correct 1 ms 1372 KB Output is correct
10 Correct 1 ms 1372 KB Output is correct
11 Correct 1 ms 1368 KB Output is correct
12 Correct 1 ms 1368 KB Output is correct
13 Correct 1 ms 1372 KB Output is correct
14 Correct 1 ms 1372 KB Output is correct
15 Correct 1 ms 1372 KB Output is correct
16 Correct 1 ms 1372 KB Output is correct
17 Correct 1 ms 1372 KB Output is correct
18 Correct 1 ms 1372 KB Output is correct
19 Correct 1 ms 1372 KB Output is correct
20 Correct 1 ms 1372 KB Output is correct
21 Correct 2 ms 1536 KB Output is correct
22 Correct 2 ms 1372 KB Output is correct
23 Correct 1 ms 1384 KB Output is correct
24 Correct 2 ms 1372 KB Output is correct
25 Correct 1 ms 1372 KB Output is correct
26 Correct 1 ms 1372 KB Output is correct
27 Correct 1 ms 1372 KB Output is correct
28 Correct 1 ms 1372 KB Output is correct
29 Correct 1 ms 1372 KB Output is correct

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1372 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 1 ms 1372 KB Output is correct
4 Correct 1 ms 1372 KB Output is correct
5 Correct 1 ms 1372 KB Output is correct
6 Correct 1 ms 1372 KB Output is correct
7 Correct 1 ms 1372 KB Output is correct
8 Correct 1 ms 1372 KB Output is correct
9 Correct 1 ms 1372 KB Output is correct
10 Correct 1 ms 1372 KB Output is correct
11 Correct 1 ms 1368 KB Output is correct
12 Correct 1 ms 1368 KB Output is correct
13 Correct 1 ms 1372 KB Output is correct
14 Correct 1 ms 1372 KB Output is correct
15 Correct 1 ms 1372 KB Output is correct
16 Correct 1 ms 1372 KB Output is correct
17 Correct 1 ms 1372 KB Output is correct
18 Correct 1 ms 1372 KB Output is correct
19 Correct 1 ms 1372 KB Output is correct
20 Correct 1 ms 1372 KB Output is correct
21 Correct 2 ms 1536 KB Output is correct
22 Correct 2 ms 1372 KB Output is correct
23 Correct 1 ms 1384 KB Output is correct
24 Correct 2 ms 1372 KB Output is correct
25 Correct 1 ms 1372 KB Output is correct
26 Correct 1 ms 1372 KB Output is correct
27 Correct 1 ms 1372 KB Output is correct
28 Correct 1 ms 1372 KB Output is correct
29 Correct 1 ms 1372 KB Output is correct
30 Correct 207 ms 66008 KB Output is correct
31 Correct 180 ms 50456 KB Output is correct
32 Execution timed out 2079 ms 86396 KB Time limit exceeded
33 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1372 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 1 ms 1368 KB Output is correct
4 Correct 1 ms 1372 KB Output is correct
5 Correct 2 ms 1372 KB Output is correct
6 Correct 2 ms 1372 KB Output is correct
7 Correct 1 ms 1372 KB Output is correct
8 Correct 1 ms 1532 KB Output is correct
9 Correct 1 ms 1372 KB Output is correct
10 Correct 2 ms 1624 KB Output is correct
11 Correct 3 ms 1372 KB Output is correct
12 Correct 2 ms 1500 KB Output is correct
13 Correct 2 ms 1372 KB Output is correct
14 Correct 1 ms 1372 KB Output is correct
15 Correct 2 ms 1372 KB Output is correct
16 Correct 1 ms 1372 KB Output is correct
17 Correct 3 ms 1372 KB Output is correct
18 Correct 2 ms 1624 KB Output is correct
19 Correct 2 ms 1372 KB Output is correct
20 Correct 1 ms 1372 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1372 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 1 ms 1372 KB Output is correct
4 Correct 1 ms 1372 KB Output is correct
5 Correct 1 ms 1372 KB Output is correct
6 Correct 1 ms 1372 KB Output is correct
7 Correct 1 ms 1372 KB Output is correct
8 Correct 1 ms 1372 KB Output is correct
9 Correct 1 ms 1372 KB Output is correct
10 Correct 1 ms 1372 KB Output is correct
11 Correct 1 ms 1368 KB Output is correct
12 Correct 1 ms 1368 KB Output is correct
13 Correct 1 ms 1372 KB Output is correct
14 Correct 1 ms 1372 KB Output is correct
15 Correct 1 ms 1372 KB Output is correct
16 Correct 1 ms 1372 KB Output is correct
17 Correct 1 ms 1372 KB Output is correct
18 Correct 1 ms 1372 KB Output is correct
19 Correct 1 ms 1372 KB Output is correct
20 Correct 1 ms 1372 KB Output is correct
21 Correct 2 ms 1536 KB Output is correct
22 Correct 2 ms 1372 KB Output is correct
23 Correct 1 ms 1384 KB Output is correct
24 Correct 2 ms 1372 KB Output is correct
25 Correct 1 ms 1372 KB Output is correct
26 Correct 1 ms 1372 KB Output is correct
27 Correct 1 ms 1372 KB Output is correct
28 Correct 1 ms 1372 KB Output is correct
29 Correct 1 ms 1372 KB Output is correct
30 Correct 207 ms 66008 KB Output is correct
31 Correct 180 ms 50456 KB Output is correct
32 Execution timed out 2079 ms 86396 KB Time limit exceeded
33 Halted 0 ms 0 KB -