oj.uz

Submission #1012743

# Submission time Handle Problem Language Result Execution time Memory
1012743 2024-07-02T14:34:06 Z ThegeekKnight16 Ancient Books (IOI17_books) C++17
42 / 100
 2000 ms 360056 KB 
#include <bits/stdc++.h>
#include "books.h"
using namespace std;
const int INF = 0x3f3f3f3f;
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,tune=native")
vector<vector<pair<int, int>>> adj;
int create()
{
    adj.emplace_back();
    return adj.size()-1;
}

int build(int ini, int fim)
{
    if (ini == fim)
    {
        return ini;
    }

    int pos = create();
    int m = (ini + fim) >> 1;
    adj[pos].emplace_back(build(ini, m), 0);
    adj[pos].emplace_back(build(m+1, fim), 0);
    return pos;
}

void update(int pos, int ini, int fim, int p, int q, int val)
{
    if (q < ini || p > fim) return;
    if (p <= ini && fim <= q) {adj[val].emplace_back(pos, 0); return;}
    int m = (ini + fim) >> 1;
    int e = adj[pos][0].first, d = adj[pos][1].first;
    update(e, ini, m, p, q, val);
    update(d, m+1, fim, p, q, val);
}

long long minimum_walk(std::vector<int> p, int s) {
    int N = p.size();
    long long resp = 0;
    for (int i = 0; i < N; i++) resp += abs(p[i]-i);
    if (resp == 0) return 0;
    vector<int> minSuf(N); minSuf.back() = p.back();
    for (int i = N-2; i >= 0; i--) minSuf[i] = min(minSuf[i+1], p[i]);
    vector<int> maxPref(N); maxPref[0] = p[0];
    for (int i = 1; i < N; i++) maxPref[i] = max(maxPref[i-1], p[i]);
    int lastS = 0; vector<pair<int, int>> comps;
    for (int i = 1; i < N; i++) if (maxPref[i-1] < i && minSuf[i] >= i)
    {
        comps.emplace_back(lastS, i-1);
        // resp += i - lastS;
        lastS = i;
    }
    comps.emplace_back(lastS, N-1);
    while (!comps.empty() && comps.back().first == comps.back().second) comps.pop_back();
    reverse(comps.begin(), comps.end());
    while (!comps.empty() && comps.back().first == comps.back().second) comps.pop_back();
    reverse(comps.begin(), comps.end());
    for (int i = 0; i+1 < comps.size(); i++) resp += 2*(comps[i+1].first - comps[i].second);
    if (s < comps[0].first) resp += 2*(comps[0].first - s);
    else if (s > comps.back().second) resp += 2*(s - comps.back().second);
    else
    {
        //Parte ruim
        adj.resize(N);
        int root = build(0, N-1);
        for (int i = 0; i < N; i++)
        {
            int l = min(i, p[i]), r = max(i, p[i]);
            update(root, 0, N-1, l, r, i);
            if (l > 0) adj[i].emplace_back(l-1, +1);
            if (r+1 < N) adj[i].emplace_back(r+1, +1);
        }

        queue<int> q1, q2; vector<int> Marc(adj.size()), Dist(adj.size(), INF);
        q1.push(s); Dist[s] = 0;
        while (!q1.empty() || !q2.empty())
        {
            int cur;
            if (!q1.empty()) cur = q1.front(), q1.pop();
            else cur = q2.front(), q2.pop();
            if (Marc[cur]) continue;
            Marc[cur] = 1;

            for (auto [viz, p] : adj[cur])
            {
                if (Marc[viz]) continue;
                if (Dist[viz] <= Dist[cur] + p) continue;
                if (p == 0) q1.push(viz);
                else q2.push(viz);
                Dist[viz] = Dist[cur]+p;
            }
        }
        for (auto [x, y] : comps)
        {
            if (x <= s && s <= y)
            {
                resp += 2*Dist[x];
                break;
            }
        }
    }


    return resp;
}

Compilation message

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:59:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for (int i = 0; i+1 < comps.size(); i++) resp += 2*(comps[i+1].first - comps[i].second);
      |                     ~~~~^~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 1 ms 344 KB Output is correct
26 Correct 1 ms 600 KB Output is correct
27 Correct 1 ms 604 KB Output is correct
28 Correct 1 ms 604 KB Output is correct
29 Correct 1 ms 604 KB Output is correct
30 Execution timed out 2109 ms 360056 KB Time limit exceeded
31 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 1 ms 344 KB Output is correct
26 Correct 1 ms 600 KB Output is correct
27 Correct 1 ms 604 KB Output is correct
28 Correct 1 ms 604 KB Output is correct
29 Correct 1 ms 604 KB Output is correct
30 Execution timed out 2109 ms 360056 KB Time limit exceeded
31 Halted 0 ms 0 KB -