oj.uz

Submission #600837

# Submission time Handle Problem Language Result Execution time Memory
600837 2022-07-21T08:11:23 Z Lucpp Ancient Books (IOI17_books) C++17
0 / 100
 2000 ms 212 KB 
#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

long long minimum_walk(vector<int> p, int s){
	int n = (int)p.size();
	ll ans = 0;
	vector<bool> vis(n);
	int mi = s, ma = s;
	int l = s, r = s;
	while(true){
		int i = -1;
		while(r <= ma){
			if(!vis[r]){
				i = r;
				break;
			}
			r++;
		}
		if(i != -1)
		while(l >= mi){
			if(!vis[l]){
				i = l;
				break;
			}
			l--; 
		}
		if(i == -1){
			int oldR = r, oldL = l;
			while(r < n){
				if(p[r] != r){
					i = r;
					ans += 2*(r+1-oldR);
					break;
				}
				r++;
			}
			if(i == -1)
			while(l >= 0){
				if(p[l] != l){
					i = l;
					ans += 2*(oldL+1-l);
					break;
				}
				l--;
			}
			if(i == -1) break;
		}
		int j = i;
		do
		{
			vis[j] = true;
			mi = min(mi, p[j]);
			ma = max(ma, p[j]);
			ans += abs(j-p[j]);
			j = p[j];
		}while(j != i);
	}
	return ans;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Execution timed out 2077 ms 212 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Execution timed out 2077 ms 212 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Execution timed out 2077 ms 212 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2071 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Execution timed out 2077 ms 212 KB Time limit exceeded
4 Halted 0 ms 0 KB -