oj.uz

Submission #921296

# Submission time Handle Problem Language Result Execution time Memory
921296 2024-02-03T16:36:58 Z siewjh Ancient Books (IOI17_books) C++17
12 / 100
 2 ms 8024 KB 
#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1'000'005;
int cyc[MAXN], lc[MAXN], rc[MAXN];
void extend(int &cl, int &cr, int tl, int tr){
	while (cl > tl || cr < tr){
		if (cl > tl){
			cl--;
			tl = min(tl, lc[cyc[cl]]); tr = max(tr, rc[cyc[cl]]);
		}
		else{
			cr++;
			tl = min(tl, lc[cyc[cr]]); tr = max(tr, rc[cyc[cr]]);
		}
	}
}
ll minimum_walk(vector<int> p, int s) {
	int nums = p.size();
	int mn = s, mx = s;
	memset(cyc, -1, sizeof(cyc));
	ll ans = 0;
	for (int i = 0; i < nums; i++) ans += abs(i - p[i]);
	for (int i = 0; i < nums; i++)
		if (cyc[i] == -1){
			int curr = i, l = i, r = i;
			do{
				cyc[curr] = i; l = min(l, curr); r = max(r, curr);
				curr = p[curr];
			} while (curr != i);
			lc[i] = l; rc[i] = r;
			if (p[i] != i){
				mn = min(mn, l); mx = max(mx, r);
			}
		}
	int cl = lc[cyc[s]], cr = rc[cyc[s]];
	while (cl > mn || cr < mx){
		int lnl = cl, lnr = cr, le = 0;
		while (lnl > mn && lnr <= cr){
			extend(lnl, lnr, lnl - 1, lnr);
			le++;
		}
		int rnl = cl, rnr = cr, re = 0;
		while (rnr < mx && rnl >= cl){
			extend(rnl, rnr, rnl, rnr + 1);
			re++;
		}
		if (lnl == rnl && lnr == rnr){ // cross the middle
			ans += 2 * min(le, re);
			cl = lnl; cr = lnr;
		}
		else{
			ans += 2 * (le + re);
			cl = lnl; cr = rnr;
		}
	}
	return ans;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7768 KB Output is correct
2 Correct 2 ms 7768 KB Output is correct
3 Correct 2 ms 7772 KB Output is correct
4 Correct 2 ms 7924 KB Output is correct
5 Correct 2 ms 7772 KB Output is correct
6 Correct 2 ms 7772 KB Output is correct
7 Correct 2 ms 7768 KB Output is correct
8 Correct 2 ms 7772 KB Output is correct
9 Correct 2 ms 7772 KB Output is correct
10 Correct 2 ms 7768 KB Output is correct
11 Correct 2 ms 7768 KB Output is correct
12 Correct 2 ms 7772 KB Output is correct
13 Correct 2 ms 7772 KB Output is correct
14 Correct 2 ms 7772 KB Output is correct
15 Correct 2 ms 8024 KB Output is correct
16 Correct 2 ms 7772 KB Output is correct
17 Correct 2 ms 7768 KB Output is correct
18 Correct 2 ms 7772 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 28.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 7772 KB 3rd lines differ - on the 1st token, expected: '3304', found: '3308'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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