oj.uz

Submission #355449

# Submission time Handle Problem Language Result Execution time Memory
355449 2021-01-22T13:46:17 Z amunduzbaev Ancient Books (IOI17_books) C++14
0 / 100
 8 ms 4348 KB 
#include "books.h"
 
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
 
#define ll long long
#define sz(x) (int)x.size()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
 
const ll inf = 1e9+7;
const int N = 1e3+5;
const int mod = 1e9+7;
 
int n, dp[N][N], used[N], last, L[N], R[N], in[N];
int endL, endR;

pii ext(int l, int r){
	int new_l = min(L[in[l]], L[in[r]]), new_r = max(R[in[r]], R[in[l]]);
	while(1){
		if(new_l < l){
			new_l = min(L[in[--l]], new_l), new_r = max(R[in[l]], new_r);
		}else if(new_r > r){
			new_l = min(L[in[++r]], new_l), new_r = max(R[in[r]], new_r);
		}else break;
	}return {new_l, new_r};
}

ll fun(int l, int r){
	if(l < endL || r > endR) return inf;
	pii tt = ext(l, r);
	l = tt.ff, r = tt.ss;
	if(l == endL && r == endR) return 0;
	int &res = dp[l][r];
	if(res != -1) return res;
	return res = min(fun(l-1, r), fun(l, r+1)) + 2;
}

ll minimum_walk(vector<int> p, int s) {
	memset(dp, -1, sizeof dp);
	n = sz(p);
	ll res = 0;
	for(int i=0;i<n;i++){
		if(!used[i]){
			int u = i;
			L[last] = u, R[last] = u;
			do{
				used[u] = 1;
				in[u] = last;
				L[last] = min(L[last], u);
				R[last] = max(R[last], u);
				res += abs(p[u] - u);
				u = p[u];
			}while(u != i);
			endL = min(L[last], endL);
			endR = max(R[last], endR);
			last++;
		}
	} return fun(s, s) + res;
}

Subtask #1
0 / 12.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 28.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

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