Submission #660334

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
660334	2022-11-21T16:24:31 Z	urosk	Ancient Books (IOI17_books)	C++14	12 / 100	13 ms	23848 KB

books

#include "books.h"
#define dbg(x) cerr<<#x<<": "<<x<<endl
#define here cerr<<"================================\n"
#include <bits/stdc++.h>
#define ll long long
#define llinf 1000000000000000000LL
#define pb push_back
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define fi first
#define sc second
#define endl '\n'
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}

using namespace std;
#define maxn 1000005
ll n,st,it;
ll a[maxn],col[maxn],mx[maxn],mn[maxn];
vector<ll> g[maxn];
long long minimum_walk(vector<int> p, int s) {
    n = sz(p);
    for(ll i = 1;i<=n;i++) a[i] = p[i-1]+1;
    reverse(all(p));
    //if(is_sorted(all(p))&&n==4) return 8;
    st = s+1;
    ll ans = 0;
    for(ll i = 1;i<=n;i++){
        if(col[i]) continue;
        if(i==a[i]) continue;
        ll x = a[i];
        ans+=abs(i-a[i]);
        it++;
        col[i] = it;
        mx[it] = i;
        mn[it] = i;
        while(x!=i){
            mx[it] = max(mx[it],x);
            col[x] = it;
            ans+=abs(x-a[x]);
            x = a[x];
        }
    }
    set<ll> cur;
    for(ll i = 1;i<=n;i++){
        if(col[i]){
            for(ll j = 1;j<=it;j++){
                if(mn[j]>=mn[col[i]]&&mx[j]<=mx[col[i]]) cur.insert(j);
            }
        }
        if(sz(cur)==it){
            ans+=2*(i-1);
            break;
        }
    }
	return ans;
}
/*
4 0
0 2 3 1

4 0
3 2 1 0

*/

Subtask #1

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	23764 KB	Output is correct
2	Correct	11 ms	23764 KB	Output is correct
3	Correct	13 ms	23712 KB	Output is correct
4	Correct	12 ms	23764 KB	Output is correct
5	Correct	11 ms	23764 KB	Output is correct
6	Correct	12 ms	23764 KB	Output is correct
7	Correct	12 ms	23816 KB	Output is correct
8	Correct	12 ms	23716 KB	Output is correct
9	Correct	12 ms	23764 KB	Output is correct
10	Correct	12 ms	23800 KB	Output is correct
11	Correct	11 ms	23764 KB	Output is correct
12	Correct	12 ms	23756 KB	Output is correct
13	Correct	11 ms	23764 KB	Output is correct
14	Correct	12 ms	23736 KB	Output is correct
15	Correct	12 ms	23808 KB	Output is correct
16	Correct	12 ms	23820 KB	Output is correct
17	Correct	11 ms	23764 KB	Output is correct
18	Correct	12 ms	23848 KB	Output is correct

Subtask #2

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	23764 KB	Output is correct
2	Correct	11 ms	23764 KB	Output is correct
3	Correct	13 ms	23712 KB	Output is correct
4	Correct	12 ms	23764 KB	Output is correct
5	Correct	11 ms	23764 KB	Output is correct
6	Correct	12 ms	23764 KB	Output is correct
7	Correct	12 ms	23816 KB	Output is correct
8	Correct	12 ms	23716 KB	Output is correct
9	Correct	12 ms	23764 KB	Output is correct
10	Correct	12 ms	23800 KB	Output is correct
11	Correct	11 ms	23764 KB	Output is correct
12	Correct	12 ms	23756 KB	Output is correct
13	Correct	11 ms	23764 KB	Output is correct
14	Correct	12 ms	23736 KB	Output is correct
15	Correct	12 ms	23808 KB	Output is correct
16	Correct	12 ms	23820 KB	Output is correct
17	Correct	11 ms	23764 KB	Output is correct
18	Correct	12 ms	23848 KB	Output is correct
19	Incorrect	11 ms	23828 KB	3rd lines differ - on the 1st token, expected: '338572', found: '338578'
20	Halted	0 ms	0 KB	-

Subtask #3

0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	23764 KB	Output is correct
2	Correct	11 ms	23764 KB	Output is correct
3	Correct	13 ms	23712 KB	Output is correct
4	Correct	12 ms	23764 KB	Output is correct
5	Correct	11 ms	23764 KB	Output is correct
6	Correct	12 ms	23764 KB	Output is correct
7	Correct	12 ms	23816 KB	Output is correct
8	Correct	12 ms	23716 KB	Output is correct
9	Correct	12 ms	23764 KB	Output is correct
10	Correct	12 ms	23800 KB	Output is correct
11	Correct	11 ms	23764 KB	Output is correct
12	Correct	12 ms	23756 KB	Output is correct
13	Correct	11 ms	23764 KB	Output is correct
14	Correct	12 ms	23736 KB	Output is correct
15	Correct	12 ms	23808 KB	Output is correct
16	Correct	12 ms	23820 KB	Output is correct
17	Correct	11 ms	23764 KB	Output is correct
18	Correct	12 ms	23848 KB	Output is correct
19	Incorrect	11 ms	23828 KB	3rd lines differ - on the 1st token, expected: '338572', found: '338578'
20	Halted	0 ms	0 KB	-

Subtask #4

0 / 20.0

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

Subtask #5

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	23764 KB	Output is correct
2	Correct	11 ms	23764 KB	Output is correct
3	Correct	13 ms	23712 KB	Output is correct
4	Correct	12 ms	23764 KB	Output is correct
5	Correct	11 ms	23764 KB	Output is correct
6	Correct	12 ms	23764 KB	Output is correct
7	Correct	12 ms	23816 KB	Output is correct
8	Correct	12 ms	23716 KB	Output is correct
9	Correct	12 ms	23764 KB	Output is correct
10	Correct	12 ms	23800 KB	Output is correct
11	Correct	11 ms	23764 KB	Output is correct
12	Correct	12 ms	23756 KB	Output is correct
13	Correct	11 ms	23764 KB	Output is correct
14	Correct	12 ms	23736 KB	Output is correct
15	Correct	12 ms	23808 KB	Output is correct
16	Correct	12 ms	23820 KB	Output is correct
17	Correct	11 ms	23764 KB	Output is correct
18	Correct	12 ms	23848 KB	Output is correct
19	Incorrect	11 ms	23828 KB	3rd lines differ - on the 1st token, expected: '338572', found: '338578'
20	Halted	0 ms	0 KB	-