oj.uz

Submission #423685

# Submission time Handle Problem Language Result Execution time Memory
423685 2021-06-11T11:23:51 Z arayi Ancient Books (IOI17_books) C++17
50 / 100
 255 ms 39788 KB 
#include "books.h"
#include <bits/stdc++.h>
#define lli long long
#define ad push_back
#define fr first
#define sc second
#define MP make_pair
using namespace std;

const int N = 1e6 + 30;

int i1 = 1, ii, n;
int col[N], a[N], cl[N];
int mn[N], mx[N], m[N], x[N];
lli ans;
int dfs(int v)
{
    col[v] = i1;
    cl[v] = ii;
    mn[ii] = min(mn[ii], v), m[i1] = min(m[i1], v);
    mx[ii] = max(mx[ii], v), x[i1] = max(x[i1], v);
    if(!col[a[v]]) return max(v, dfs(a[v]));
    return v;
}
long long minimum_walk(vector<int> p, int s)
{
	n = p.size();
	for(int i = 0; i < n; i++) a[i] = p[i], ans += abs(a[i] - i), mn[i] = m[i] = n;
	int nx = -1;
	for(int i = 0; i < n; i++)
    {
        if(a[i] == i) continue;
        if(!col[i])
        {
            if(nx >= 0 && i > nx) ans += 2*(i - nx), i1++;
            ii++;
            nx = max(nx, dfs(i));
        }
    }
    int dz = -1, aj = -1;
    for(int i = s; i < n; i++)
    {
        if(col[i])
        {
            aj = i;
            break;
        }
    }
    for(int i = s; i >= 0; i--)
    {
        if(col[i])
        {
            dz = i;
            break;
        }
    }
    if(dz == -1 && aj == -1) return ans;
    else if(dz == -1) ans += 2*abs(aj - s);
    else if(aj == -1) ans += 2*abs(s - dz);
    else if(col[aj] == col[dz])
    {
        int sm = 0;
        int i = s, nx = s;
        while(nx < x[col[aj]])
        {
            if(cl[i]) nx = max(nx, mx[cl[i]]);
            i++;
            if(i > nx) sm++, nx = i;
        }
        int ss = 0;
        i = s, nx = s;
        while(nx > m[col[aj]])
        {
            if(cl[i]) nx = min(nx, mn[cl[i]]);
            i--;
            if(i < nx) ss++, nx = i;
        }
        ans += 2*min(ss, sm);
        //cout << s <<  " " << sm << endl;
    }
    return ans;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 255 ms 39788 KB Output is correct
31 Correct 232 ms 33740 KB Output is correct
32 Correct 148 ms 19780 KB Output is correct
33 Correct 140 ms 29048 KB Output is correct
34 Correct 137 ms 29036 KB Output is correct
35 Correct 140 ms 29380 KB Output is correct
36 Correct 181 ms 28652 KB Output is correct
37 Correct 134 ms 27768 KB Output is correct
38 Correct 143 ms 27772 KB Output is correct
39 Correct 151 ms 27716 KB Output is correct
40 Correct 139 ms 28172 KB Output is correct
41 Correct 255 ms 32836 KB Output is correct
42 Correct 165 ms 30072 KB Output is correct
43 Correct 183 ms 28656 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB 3rd lines differ - on the 1st token, expected: '3304', found: '3308'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 255 ms 39788 KB Output is correct
31 Correct 232 ms 33740 KB Output is correct
32 Correct 148 ms 19780 KB Output is correct
33 Correct 140 ms 29048 KB Output is correct
34 Correct 137 ms 29036 KB Output is correct
35 Correct 140 ms 29380 KB Output is correct
36 Correct 181 ms 28652 KB Output is correct
37 Correct 134 ms 27768 KB Output is correct
38 Correct 143 ms 27772 KB Output is correct
39 Correct 151 ms 27716 KB Output is correct
40 Correct 139 ms 28172 KB Output is correct
41 Correct 255 ms 32836 KB Output is correct
42 Correct 165 ms 30072 KB Output is correct
43 Correct 183 ms 28656 KB Output is correct
44 Incorrect 1 ms 332 KB 3rd lines differ - on the 1st token, expected: '3304', found: '3308'
45 Halted 0 ms 0 KB -