Submission #660331

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
660331	2022-11-21T16:18:13 Z	urosk	Ancient Books (IOI17_books)	C++14	12 / 100	15 ms	23804 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];
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;
        while(x!=i){
            col[x] = it;
            ans+=abs(x-a[x]);
            x = a[x];
        }
    }
    set<ll> cur;
    for(ll i = 1;i<=n;i++){
        if(col[i]) cur.insert(col[i]);
        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	15 ms	23780 KB	Output is correct
2	Correct	14 ms	23688 KB	Output is correct
3	Correct	12 ms	23784 KB	Output is correct
4	Correct	12 ms	23764 KB	Output is correct
5	Correct	12 ms	23804 KB	Output is correct
6	Correct	12 ms	23764 KB	Output is correct
7	Correct	12 ms	23800 KB	Output is correct
8	Correct	12 ms	23764 KB	Output is correct
9	Correct	12 ms	23764 KB	Output is correct
10	Correct	12 ms	23716 KB	Output is correct
11	Correct	13 ms	23764 KB	Output is correct
12	Correct	13 ms	23796 KB	Output is correct
13	Correct	14 ms	23764 KB	Output is correct
14	Correct	12 ms	23792 KB	Output is correct
15	Correct	12 ms	23764 KB	Output is correct
16	Correct	12 ms	23704 KB	Output is correct
17	Correct	12 ms	23764 KB	Output is correct
18	Correct	12 ms	23772 KB	Output is correct

Subtask #2

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	23780 KB	Output is correct
2	Correct	14 ms	23688 KB	Output is correct
3	Correct	12 ms	23784 KB	Output is correct
4	Correct	12 ms	23764 KB	Output is correct
5	Correct	12 ms	23804 KB	Output is correct
6	Correct	12 ms	23764 KB	Output is correct
7	Correct	12 ms	23800 KB	Output is correct
8	Correct	12 ms	23764 KB	Output is correct
9	Correct	12 ms	23764 KB	Output is correct
10	Correct	12 ms	23716 KB	Output is correct
11	Correct	13 ms	23764 KB	Output is correct
12	Correct	13 ms	23796 KB	Output is correct
13	Correct	14 ms	23764 KB	Output is correct
14	Correct	12 ms	23792 KB	Output is correct
15	Correct	12 ms	23764 KB	Output is correct
16	Correct	12 ms	23704 KB	Output is correct
17	Correct	12 ms	23764 KB	Output is correct
18	Correct	12 ms	23772 KB	Output is correct
19	Incorrect	12 ms	23788 KB	3rd lines differ - on the 1st token, expected: '338572', found: '338864'
20	Halted	0 ms	0 KB	-

Subtask #3

0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	23780 KB	Output is correct
2	Correct	14 ms	23688 KB	Output is correct
3	Correct	12 ms	23784 KB	Output is correct
4	Correct	12 ms	23764 KB	Output is correct
5	Correct	12 ms	23804 KB	Output is correct
6	Correct	12 ms	23764 KB	Output is correct
7	Correct	12 ms	23800 KB	Output is correct
8	Correct	12 ms	23764 KB	Output is correct
9	Correct	12 ms	23764 KB	Output is correct
10	Correct	12 ms	23716 KB	Output is correct
11	Correct	13 ms	23764 KB	Output is correct
12	Correct	13 ms	23796 KB	Output is correct
13	Correct	14 ms	23764 KB	Output is correct
14	Correct	12 ms	23792 KB	Output is correct
15	Correct	12 ms	23764 KB	Output is correct
16	Correct	12 ms	23704 KB	Output is correct
17	Correct	12 ms	23764 KB	Output is correct
18	Correct	12 ms	23772 KB	Output is correct
19	Incorrect	12 ms	23788 KB	3rd lines differ - on the 1st token, expected: '338572', found: '338864'
20	Halted	0 ms	0 KB	-

Subtask #4

0 / 20.0

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

Subtask #5

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	23780 KB	Output is correct
2	Correct	14 ms	23688 KB	Output is correct
3	Correct	12 ms	23784 KB	Output is correct
4	Correct	12 ms	23764 KB	Output is correct
5	Correct	12 ms	23804 KB	Output is correct
6	Correct	12 ms	23764 KB	Output is correct
7	Correct	12 ms	23800 KB	Output is correct
8	Correct	12 ms	23764 KB	Output is correct
9	Correct	12 ms	23764 KB	Output is correct
10	Correct	12 ms	23716 KB	Output is correct
11	Correct	13 ms	23764 KB	Output is correct
12	Correct	13 ms	23796 KB	Output is correct
13	Correct	14 ms	23764 KB	Output is correct
14	Correct	12 ms	23792 KB	Output is correct
15	Correct	12 ms	23764 KB	Output is correct
16	Correct	12 ms	23704 KB	Output is correct
17	Correct	12 ms	23764 KB	Output is correct
18	Correct	12 ms	23772 KB	Output is correct
19	Incorrect	12 ms	23788 KB	3rd lines differ - on the 1st token, expected: '338572', found: '338864'
20	Halted	0 ms	0 KB	-