oj.uz

Submission #425873

# Submission time Handle Problem Language Result Execution time Memory
425873 2021-06-13T12:08:13 Z 2fat2code Ancient Books (IOI17_books) C++17
50 / 100
 326 ms 66648 KB 
#include "books.h"
#include<bits/stdc++.h>
#define fr first
#define sc second
#define LL long long
#define all(s) s.begin(), s.end()
using namespace std;

const int nmax = 1000005;

long long n, comp, l_ned, r_ned, ans, viz[nmax];
vector<long long>cicles[nmax];

void extend(LL &l, LL &r, LL &ll, LL &rr){
    while(l > ll || r < rr){
        if(l > ll){
            --l;
            ll = min(ll, cicles[viz[l]][0]);
            rr = max(rr, cicles[viz[l]].back());
        }
        else if(r < rr){
            ++r;
            ll = min(ll, cicles[viz[r]][0]);
            rr = max(rr, cicles[viz[r]].back());
        }
    }
}

void compute(int s){
    LL l = s, r = s, ll = cicles[viz[s]][0], rr = cicles[viz[s]].back();
    extend(l, r, ll, rr);
    while(ll > 0 || rr < n - 1){
        LL calcright = 0, maxi = -1, findright = 0;
        for(int i=rr+1;i<=n-1;i++){
            if(i == cicles[viz[i]][0] && i > maxi){
                calcright += 2LL;
            }
            maxi = max(maxi, cicles[viz[i]].back());
            if(cicles[viz[i]][0] < ll){
                findright = viz[i];
                break;
            }
        }
        if(!findright){
            rr = n - 1;
            ans += calcright;
        }
        LL calcleft = 0, mini = n, findleft = 0;
        for(int i=ll-1;i>=0;i--){
            if(i == cicles[viz[i]].back() && i < mini){
                calcleft += 2LL;
            }
            mini = min(mini, cicles[viz[i]][0]);
            if(cicles[viz[i]].back() > rr){
                findleft = viz[i];
                break;
            }
        }
        if(!findleft){
            ll = 0;
            ans += calcleft;
        }
        else{
            ans += min(calcleft, calcright);
            if(calcleft > calcright){
                ll = min(ll, cicles[findright][0]);
                rr = max(rr, cicles[findright].back());
            }
            else{
                ll = min(ll, cicles[findleft][0]);
                rr = max(rr, cicles[findleft].back());
            }
        }
        extend(l, r, ll, rr);
    }
}

long long minimum_walk(vector<int> p, int s) {
    n = (int)p.size();
	while(p[l_ned] == l_ned && s > l_ned) l_ned++;
	r_ned = n - 1;
	while(p[r_ned] == r_ned && s < r_ned) r_ned--;
	vector<int>aux;
	for(int i=l_ned;i<=r_ned;i++){
        aux.push_back(p[i] - l_ned);
	}
	swap(aux, p);
	s -= l_ned;
	n = (int)p.size();

	for(int i=0;i<n;i++){
        ans += abs(i - p[i]);
	}
	for(int i=0;i<n;i++){
        if(!viz[i]){
            ++comp;
            viz[i] = comp;
            cicles[comp].push_back(i);
            int curr = p[i];
            while(curr  !=  i){
                viz[curr] = comp;
                cicles[comp].push_back(curr);
                curr = p[curr];
            }
        }
	}
	for(int i=1;i<=comp;i++){
        sort(all(cicles[i]));
	}
	compute(s);
    return ans;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23732 KB Output is correct
2 Correct 18 ms 23756 KB Output is correct
3 Correct 17 ms 23784 KB Output is correct
4 Correct 17 ms 23756 KB Output is correct
5 Correct 17 ms 23756 KB Output is correct
6 Correct 13 ms 23756 KB Output is correct
7 Correct 13 ms 23784 KB Output is correct
8 Correct 15 ms 23744 KB Output is correct
9 Correct 14 ms 23780 KB Output is correct
10 Correct 16 ms 23700 KB Output is correct
11 Correct 15 ms 23704 KB Output is correct
12 Correct 16 ms 23832 KB Output is correct
13 Correct 15 ms 23772 KB Output is correct
14 Correct 15 ms 23756 KB Output is correct
15 Correct 14 ms 23756 KB Output is correct
16 Correct 16 ms 23788 KB Output is correct
17 Correct 15 ms 23676 KB Output is correct
18 Correct 14 ms 23756 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23732 KB Output is correct
2 Correct 18 ms 23756 KB Output is correct
3 Correct 17 ms 23784 KB Output is correct
4 Correct 17 ms 23756 KB Output is correct
5 Correct 17 ms 23756 KB Output is correct
6 Correct 13 ms 23756 KB Output is correct
7 Correct 13 ms 23784 KB Output is correct
8 Correct 15 ms 23744 KB Output is correct
9 Correct 14 ms 23780 KB Output is correct
10 Correct 16 ms 23700 KB Output is correct
11 Correct 15 ms 23704 KB Output is correct
12 Correct 16 ms 23832 KB Output is correct
13 Correct 15 ms 23772 KB Output is correct
14 Correct 15 ms 23756 KB Output is correct
15 Correct 14 ms 23756 KB Output is correct
16 Correct 16 ms 23788 KB Output is correct
17 Correct 15 ms 23676 KB Output is correct
18 Correct 14 ms 23756 KB Output is correct
19 Correct 16 ms 23732 KB Output is correct
20 Correct 15 ms 23704 KB Output is correct
21 Correct 13 ms 23752 KB Output is correct
22 Correct 15 ms 23756 KB Output is correct
23 Correct 15 ms 23756 KB Output is correct
24 Correct 15 ms 23756 KB Output is correct
25 Correct 16 ms 23780 KB Output is correct
26 Correct 15 ms 23756 KB Output is correct
27 Correct 15 ms 23756 KB Output is correct
28 Correct 15 ms 23756 KB Output is correct
29 Correct 16 ms 23756 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23732 KB Output is correct
2 Correct 18 ms 23756 KB Output is correct
3 Correct 17 ms 23784 KB Output is correct
4 Correct 17 ms 23756 KB Output is correct
5 Correct 17 ms 23756 KB Output is correct
6 Correct 13 ms 23756 KB Output is correct
7 Correct 13 ms 23784 KB Output is correct
8 Correct 15 ms 23744 KB Output is correct
9 Correct 14 ms 23780 KB Output is correct
10 Correct 16 ms 23700 KB Output is correct
11 Correct 15 ms 23704 KB Output is correct
12 Correct 16 ms 23832 KB Output is correct
13 Correct 15 ms 23772 KB Output is correct
14 Correct 15 ms 23756 KB Output is correct
15 Correct 14 ms 23756 KB Output is correct
16 Correct 16 ms 23788 KB Output is correct
17 Correct 15 ms 23676 KB Output is correct
18 Correct 14 ms 23756 KB Output is correct
19 Correct 16 ms 23732 KB Output is correct
20 Correct 15 ms 23704 KB Output is correct
21 Correct 13 ms 23752 KB Output is correct
22 Correct 15 ms 23756 KB Output is correct
23 Correct 15 ms 23756 KB Output is correct
24 Correct 15 ms 23756 KB Output is correct
25 Correct 16 ms 23780 KB Output is correct
26 Correct 15 ms 23756 KB Output is correct
27 Correct 15 ms 23756 KB Output is correct
28 Correct 15 ms 23756 KB Output is correct
29 Correct 16 ms 23756 KB Output is correct
30 Correct 326 ms 53140 KB Output is correct
31 Correct 320 ms 52900 KB Output is correct
32 Correct 127 ms 31540 KB Output is correct
33 Correct 269 ms 66444 KB Output is correct
34 Correct 241 ms 66452 KB Output is correct
35 Correct 318 ms 63376 KB Output is correct
36 Correct 251 ms 58132 KB Output is correct
37 Correct 230 ms 54928 KB Output is correct
38 Correct 209 ms 54160 KB Output is correct
39 Correct 247 ms 53952 KB Output is correct
40 Correct 227 ms 52680 KB Output is correct
41 Correct 308 ms 53012 KB Output is correct
42 Correct 270 ms 52776 KB Output is correct
43 Correct 222 ms 66648 KB Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23732 KB Output is correct
2 Correct 18 ms 23756 KB Output is correct
3 Correct 17 ms 23784 KB Output is correct
4 Correct 17 ms 23756 KB Output is correct
5 Correct 17 ms 23756 KB Output is correct
6 Correct 13 ms 23756 KB Output is correct
7 Correct 13 ms 23784 KB Output is correct
8 Correct 15 ms 23744 KB Output is correct
9 Correct 14 ms 23780 KB Output is correct
10 Correct 16 ms 23700 KB Output is correct
11 Correct 15 ms 23704 KB Output is correct
12 Correct 16 ms 23832 KB Output is correct
13 Correct 15 ms 23772 KB Output is correct
14 Correct 15 ms 23756 KB Output is correct
15 Correct 14 ms 23756 KB Output is correct
16 Correct 16 ms 23788 KB Output is correct
17 Correct 15 ms 23676 KB Output is correct
18 Correct 14 ms 23756 KB Output is correct
19 Correct 16 ms 23732 KB Output is correct
20 Correct 15 ms 23704 KB Output is correct
21 Correct 13 ms 23752 KB Output is correct
22 Correct 15 ms 23756 KB Output is correct
23 Correct 15 ms 23756 KB Output is correct
24 Correct 15 ms 23756 KB Output is correct
25 Correct 16 ms 23780 KB Output is correct
26 Correct 15 ms 23756 KB Output is correct
27 Correct 15 ms 23756 KB Output is correct
28 Correct 15 ms 23756 KB Output is correct
29 Correct 16 ms 23756 KB Output is correct
30 Correct 326 ms 53140 KB Output is correct
31 Correct 320 ms 52900 KB Output is correct
32 Correct 127 ms 31540 KB Output is correct
33 Correct 269 ms 66444 KB Output is correct
34 Correct 241 ms 66452 KB Output is correct
35 Correct 318 ms 63376 KB Output is correct
36 Correct 251 ms 58132 KB Output is correct
37 Correct 230 ms 54928 KB Output is correct
38 Correct 209 ms 54160 KB Output is correct
39 Correct 247 ms 53952 KB Output is correct
40 Correct 227 ms 52680 KB Output is correct
41 Correct 308 ms 53012 KB Output is correct
42 Correct 270 ms 52776 KB Output is correct
43 Correct 222 ms 66648 KB Output is correct
44 Incorrect 14 ms 23756 KB 3rd lines differ - on the 1st token, expected: '3304', found: '3302'
45 Halted 0 ms 0 KB -