oj.uz

Submission #568984

# Submission time Handle Problem Language Result Execution time Memory
568984 2022-05-26T12:02:43 Z Siffer Ancient Books (IOI17_books) C++14
0 / 100
 1 ms 212 KB 
#include "books.h"
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define F first
#define S second
#define vi vector<int>
#define ii pair<int, int>

ii explore(int f1, int f2, int t2, int t1, vi &mi, vi &ma, vi &c) {
	int f3 = f1;
	int t3 = t1;
	for(int i = f1; i <= t1; i++) {
		if(i == f2) {
			i = t2+1;
			if(i > t1) continue;
		}
		f3 = min(f3, mi[c[i]]);
		t3 = max(t3, ma[c[i]]);
	}
	if(f3 == f1 && t3 == t1) return {f1, t1};
	return explore(f3, f1, t1, t3, mi, ma, c);
}

ll minimum_walk(vi p, int s) {
	int n = p.size();
	ll res = 0;
	vi c(n,-1), mi(n, n), ma(n, 0);
	for(int i = 0; i < n; i++) {
		if(c[i] == -1) {
			int k = p[i];
			c[i] = i;
			mi[i] = i;
			ma[i] = i;
			res += p[i] - i;
			while(k != i) {
				c[k] = i;
				res += abs(p[k]-k);
				mi[i] = min(mi[i], k);
				ma[i] = max(mi[i], k);
				k = p[k];
			}
		}
	}
	ii lr = explore(s,-1,-1,s,mi,ma,c);
	int l = lr.F; int r = lr.S;
	ll lc = 0; ll rc = 0;
	while(l || r < n-1) {
		bool b = 1;
		if(l) {
			lc += 2;
			lr = explore(l-1,l,r,r,mi,ma,c);
			l = lr.F;
			if(lr.S > r) {
				r = lr.S;
				b = 0;
				res += lc;
				rc = 0;
				lc = 0;
			}
		}
		if(r < n-1 && b) {
			rc += 2;
			lr = explore(l,l,r,r+1,mi,ma,c);
			r = lr.S;
			if(lr.F < l) {
				l = lr.F;
				res += rc;
				rc = 0;
				lc = 0;
			}
		}
	}
	return res + lc + rc;
}

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 Incorrect 1 ms 212 KB 3rd lines differ - on the 1st token, expected: '8', found: '10'
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 Incorrect 1 ms 212 KB 3rd lines differ - on the 1st token, expected: '8', found: '10'
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 Incorrect 1 ms 212 KB 3rd lines differ - on the 1st token, expected: '8', found: '10'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB 3rd lines differ - on the 1st token, expected: '3304', found: '3306'
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 Incorrect 1 ms 212 KB 3rd lines differ - on the 1st token, expected: '8', found: '10'
4 Halted 0 ms 0 KB -