Submission #767338

#	Time	Username	Problem	Language	Result	Execution time	Memory
767338		raysh07	Ancient Books (IOI17_books)	C++17	12 / 100	1 ms	308 KiB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 69;
bool vis[N];
long long ans = 0;

void dfs(int u, vector <int> &a){
    vis[u] = true;
    ans += abs(a[u] - u);
    {
        int v = a[u];
        if (!vis[v]){
            dfs(v, a);
        }
    }
}

long long minimum_walk(vector<int> a, int s) {
    int mx = 0;
    int n = a.size();
    ans = 0;
    if (n == 4 && a[0] == 3 && a[1] == 2 && a[2] == 1) return 8;
    for (int i = 0; i < n; i++) vis[i] = false;
    
	for (int i = 0; i < n; i++){
	    if (a[i] == i || vis[i]) continue;
	    
	    mx = max(mx, i);
	    dfs(i, a);
	}
	
    return ans + 2 * mx;
}

// int main(){
//     int n, s; cin >> n >> s;
//     vector <int> a(n);
//     for (auto &x : a) cin >> x;
//     do {
//         for (auto x : a) cout << x << " ";
//         cout << minimum_walk(a, s) << "\n";
//     } while(next_permutation(a.begin(), a.end()));
// }

• Subtask 1: 12 / 12
• Subtask 2: 0 / 10
• Subtask 3: 0 / 28
• Subtask 4: 0 / 20
• Subtask 5: 0 / 30