oj.uz

Submission #137395

# Submission time Handle Problem Language Result Execution time Memory
137395 2019-07-27T14:59:07 Z wilwxk Ancient Books (IOI17_books) C++14
12 / 100
 2000 ms 380 KB 
#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN=1e6+6;
vector<int> v;
int n, ori, atual, bons;
ll respf, ciclos;

bool melhora() {
	if(atual>=n) return 0;
	while(bons<n&&v[atual]==atual) atual++;
	// printf("atual %d\n", atual);

	int mao=v[atual];
	v[atual]=-1;
	while(mao!=-1) {
		respf+=abs(mao-atual);
		atual=mao;
		swap(mao, v[atual]);
		if(v[atual]==atual) bons++;
	}
	// for(auto cur : v) printf("%d ", cur);
	// printf(" >> %lld // %d\n", respf, atual);
	return 1;
}

long long minimum_walk(std::vector<int> P, int S) {
	n=P.size(); v=P; ori=S; atual=ori;
	for(int i=0; i<n; i++) if(v[i]==i) bons++;

	while(bons<n&&v[atual]==atual) atual++, respf++;
	while(bons<n) melhora(), ciclos++;
	respf+=abs(atual-ori);

	// printf("%lld // %d\n", respf, ciclos);
	respf-=max(0LL, (ciclos-1));
	return respf;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 252 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 3 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 256 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 380 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 252 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 3 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 256 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 380 KB Output is correct
19 Incorrect 3 ms 376 KB 3rd lines differ - on the 1st token, expected: '338572', found: '338710'
20 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 252 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 3 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 256 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 380 KB Output is correct
19 Incorrect 3 ms 376 KB 3rd lines differ - on the 1st token, expected: '338572', found: '338710'
20 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 252 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 3 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 256 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 380 KB Output is correct
19 Incorrect 3 ms 376 KB 3rd lines differ - on the 1st token, expected: '338572', found: '338710'
20 Halted 0 ms 0 KB -