답안 #1041092

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1041092 2024-08-01T15:31:58 Z ReLice 고대 책들 (IOI17_books) C++17
42 / 100
152 ms 50436 KB
#include "books.h"
#include <bits/stdc++.h>
#define ll int
#define str string
#define ins insert
#define ld long double
#define pb push_back
#define pf push_front
#define pof pop_front()
#define pob pop_back()
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define sz size()
#define vll vector<ll>
#define bc back()
#define arr array
#define pll vector<pair<ll,ll>>
using namespace std;		
const ll inf=1e9;
long long minimum_walk(vector<int> p, int s) {
	ll i;
	ll n=p.sz;
	vll l(n,-1);
	vll r(n,-1);
	ll mn=inf,mx=0;
	vll cur;
	ll ans=0;
	
	function<void(ll)> get_cycle = [&](ll v){
		if(cur.sz && v==cur[0])return;
		cur.pb(v);
		get_cycle(p[v]);
	};
	
	for(i=0;i<n;i++){
		ans+=abs(i-p[i]);
		if(l[i]!=-1)continue;
		
		get_cycle(i);
		
		sort(all(cur));
		for(auto j : cur){
			l[j]=cur[0];
			r[j]=cur.bc;
		}
		
		if(cur.sz>1){
			mn=min(mn,cur[0]);
			mx=max(mx,cur.bc);
		}
		cur.clear();
	}
	ll L=s,R=s;
	vll v;
	vector<bool> vis(n,0);
	while(L>mn || R<mx){
		while(v.size()){
			ll x=v.bc;
			v.pob;
			while(L>l[x]){
				L--;
				if(!vis[l[L]]){
					vis[l[L]]=1;
					v.pb(L);
				}
			}
			while(R<r[x]){
				R++;
				if(!vis[l[R]]){
					vis[l[R]]=1;
					v.pb(R);
				}
			}
		}
		
		
		ll nl=L,nr=R;
		ll free=L;
		ll c=0,c2=0;
		
		while(nl>mn){
			if(r[nl]>R) break;
			
			free=min(free,l[nl]);
			if(free==nl) c+=2;
			
			nl--;
		}
		
		free=R;
		while(nr<mx){
			if(l[nr]<L)break;
			
			free=max(free,r[nr]);
			if(free==nr) c2+=2;
			
			nr++;
		}
		
		
		if(l[nr]<L && r[nl]>R){
			if(c<c2){
				ans+=c;
				L=nl;
				v.pb(nl);
			}else{
				ans+=c2;
				R=nr;
				v.pb(nr);
			}
		}else if(r[nl]>R){
			R=nr;
			ans+=c2;
			
			ans+=c;
			L=nl;
			v.pb(nl);
		}else{
			L=nl;
			ans+=c;
			
			ans+=c2;
			R=nr;
			v.pb(nr);
		}
		
	}
	return ans;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 360 KB Output is correct
15 Correct 0 ms 436 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 360 KB Output is correct
15 Correct 0 ms 436 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 604 KB Output is correct
26 Correct 1 ms 432 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 360 KB Output is correct
15 Correct 0 ms 436 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 604 KB Output is correct
26 Correct 1 ms 432 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Incorrect 152 ms 50436 KB 3rd lines differ - on the 1st token, expected: '333035179244', found: '-1972269844'
31 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 444 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 360 KB Output is correct
15 Correct 0 ms 436 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 604 KB Output is correct
26 Correct 1 ms 432 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Incorrect 152 ms 50436 KB 3rd lines differ - on the 1st token, expected: '333035179244', found: '-1972269844'
31 Halted 0 ms 0 KB -