oj.uz

Submission #821309

# Submission time Handle Problem Language Result Execution time Memory
821309 2023-08-11T08:59:20 Z vjudge1 Ancient Books (IOI17_books) C++17
0 / 100
 1 ms 468 KB 
#include "books.h"
#include<bits/stdc++.h>

using namespace std;


long long minimum_walk(vector<int> p, int s) {
	int n = (int)p.size();
	bool us[n] = {};
	vector<vector<int>> cmps;
	int sum = 0;
	for(int i = 0; i < n; i++) {
		sum += abs(p[i] - i);
		if(us[i]) continue;
		int x = i;
		cmps.push_back({});
		while(!us[x]) {
			us[x] = 1;
			cmps.back().push_back(x);
			x = p[x];
		}
	}	
	if((int)cmps.size() == 1) 
		return sum;
	if(n == 2) 
		return 0;
	
	if(n == 3) {
		int l = 0;
		while(l < n && p[l] == l) l++;
		return sum + 2 * l;
	}
	if(n == 4) {
		if((int)cmps.size() == 4) 
			return 0;
		if((int)cmps.size() == 3) {
			int l = 0;
			while(l < n && p[l] == l) l++;
			return sum + 2 * l;
		}
		if((int)cmps.size() == 1) 
			return sum;
		int mx = 0;
		for(auto v : cmps) 
			mx = max(mx, (int)v.size());
		if(mx > 2) {
			int l = 0;
			while(l < n && p[l] == l) l++;
			return sum + 2 * l;
		}
		if(cmps[0].back() < cmps[1][0]) 
			return sum + 2;
		return sum + 1;
	}
}

Compilation message

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:10:22: warning: control reaches end of non-void function [-Wreturn-type]
   10 |  vector<vector<int>> cmps;
      |                      ^~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 0 ms 212 KB 3rd lines differ - on the 1st token, expected: '8', found: '9'
7 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 0 ms 212 KB 3rd lines differ - on the 1st token, expected: '8', found: '9'
7 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 0 ms 212 KB 3rd lines differ - on the 1st token, expected: '8', found: '9'
7 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 0 ms 212 KB 3rd lines differ - on the 1st token, expected: '8', found: '9'
7 Halted 0 ms 0 KB -