oj.uz

Submission #1012206

# Submission time Handle Problem Language Result Execution time Memory
1012206 2024-07-01T19:44:55 Z hyakup Ancient Books (IOI17_books) C++17
0 / 100
 1 ms 344 KB 
#include "books.h"
#include <bits/stdc++.h>
using namespace std;
#define bug(x) cout << #x << " " << x << endl;
#define ll long long

const ll maxn = 1e6 + 10;

bool marc[maxn], especial[maxn];
int bit[maxn];

void update( int id, int val ){ for( int i = id + 1; i < maxn; i += i&-i ) bit[i] += val; }
int query( int id ){ int sum = 0; for( int i = id + 1; i > 0; i -= i&-i ) sum += bit[i]; return sum; }

long long minimum_walk(vector<int> p, int s) {
	if( is_sorted( p.begin(), p.end() ) ) return 0;
	ll n = (ll)p.size();
	ll resp = 0;
	for( ll i = 0; i < (ll)p.size(); i++ ) resp += (ll)abs(p[i] - i);
	ll maxi = -1;
	bool contido = false;
	for( ll i = 0; i < n; i++ ) if( !marc[i] && p[i] != i ){
		bool good = false;
		if( maxi != -1 && i > maxi ){
			resp += 2LL*(i - maxi);
			good = true;
		}
		ll cur = i;
		int aux = query(i);
		while( !marc[cur] ){
			maxi = max( maxi, cur );
			marc[cur] = true;
			if( query(cur) != aux ) good = true;
			cur = p[cur];
		}
		if( i <= s && s <= maxi ) contido = true;

		if( good ){
			cur = i;
			while( !especial[cur] ){
				especial[cur] = true;
				update( cur, 1 );
				cur = p[cur];
			}
		}
	}

	ll l = s, r = s;
	while( l >= 0 && !especial[l] ) l--;
	while( r < n && !especial[r] ) r++;
	if( contido ) resp += 2LL*min( s - l, r - s );
	else{
		if( l == -1 ) resp += 2LL*(r - s);
		else if( r == n ) resp += 2LL*(s - l);
	}
	return resp;
}

Subtask #1
0 / 12.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 28.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

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