Submission #792231

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
792231	2023-07-24T19:45:02 Z	lollipop	Ancient Books (IOI17_books)	C++17	50 / 100	841 ms	245780 KB

books

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define ll long long
#define pb push_back
#define s second
#define f first
#define pf push_front
#define inf 100000000000000000
#define bitebi __builtin_popcountll
#define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
#define YES cout <<"YES\n"
#define NO cout << "NO\n"
#define debug cout << "Here Fine" << endl ;
#define pr pair < int , int >
#define fbo find_by_order // returns iterator
#define ook order_of_key // returns strictly less numbers than key
using namespace std ;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const double Pi=acos(-1.0);
const double EPS=1E-8;
const int mod =  1000000007 ;
const int mod1 = 998244353 ;
const int N = 2e6 + 10 ;
mt19937 R(time(0));
map < int , int > ma , ma1 ;
#include "books.h"

int pos[ N ] , been[ N ] , s , tt = 0 ;
vector < int > v[ N ] ; 
vector < int > vu ; 
ll get( int node ){
      if( node == s ) tt = 1 ; 
	been[ node ] = 1 ;
	vu.pb( node ) ; 
	ll cur = 0 ; 
	for( auto x : v[ node ] ){
//	      cout << node << " " << x << endl ;
		cur = cur + abs( x - node ) ;
		if( been[ x ] == 0 ) cur += get( x ) ; 
	}
	return cur ;
}
vector < vector < int > > vvv ;
int roca_mtvare_varskvlavebs_naxavs = 0 ; 
map < int , int > mtvare ; 
long long minimum_walk(std::vector<int> p, int S){
       s = S ; 
	 int n = p.size() ;
	 ll ans = 0 ;
	 FOR( i , n ){
		v[ i ].pb( p[ i ] ) ;  
	 } 
	 set < int > se ;
	 pair < int , int > pp ; 
	 FOR( i , n ){
	 	if( been[ i ] == 1 ) continue ;
	 	tt = 0 ; 
	 	vu.clear() ; 
	 	ans += get( i ) ; 	 	
	 	sort( vu.begin() , vu.end() ) ; 
	 	int l = vu[ 0 ] ; 
	 	int r = vu[ vu.size() - 1 ] ;
	 //	cout << l << " " << r << endl ; 
	 	 if( tt == 1 ){
	 	      pp = { l , r } ; 
	 	 }
	 	 else{
	 	   	for( auto x : vu ) mtvare[ x ] = roca_mtvare_varskvlavebs_naxavs , se.insert( x ) ;  
	 	   	vvv.pb( vu ) ; 
	 	   	roca_mtvare_varskvlavebs_naxavs ++ ; 
		 }
	 }
	 //cout << ans << endl ; 
	 int mx = 0 ; 
	 int lst = n - 1 ; 
	 while( true ){
	       int p ; 
	       if( se.size() == 0 ) break ; 
	       p = *(--se.end() ) ;
	       if( p <= pp.s ) break ; 
	       if( vvv[ mtvare[ p ] ].size() == 1 && p == lst ){
	             lst -- ; 
	             se.erase( --se.end() ) ; 
	       } else break ; 
	 }
	 int ff = 0 ;
	 while( true ){
	       int p ; 
	       if( se.size() == 0 ) break ; 
	       p = *se.begin() ; 
	       if( p >= pp.f ) break ; 
	       if( vvv[ mtvare[ p ] ].size() == 1 && p == ff ){
	             ff ++ ; se.erase( se.begin() ) ; 
	       }
	       else break ;
	 }
	 
	 int l = pp.f , r = pp.s ; 
	 while( true ){
	 	if( se.size() == 0 ) break ;
	 	int left = - INT_MAX + 5 * N , right = INT_MAX - 5 * N ;
	 	if( *se.begin() < l ) left = *( -- se.lower_bound( l ) ) ;
	 	if( *(--se.end() ) > l ) right = *se.lower_bound( l ) ;
	 	if( l - left < right - r ){
	 	    ans = ans + max( 0 , ( l - left ) * 2 ) ; 
	 	    int mn = INT_MAX , mx = 0 ; 
			for( auto x : vvv[ mtvare[ left ] ] ){
				se.erase( se.find( x ) ) ;
				mn = min( mn , x ) ;
				mx = max( mx , x ) ; 
			} 	
			l = min( mn , l ) ;
			r = max( mx , r ) ;
		}
		else{
	 	    ans = ans + max( 0 , ( right - r ) * 2 ) ; 
	 	    int mn = INT_MAX , mx = 0 ; 
			for( auto x : vvv[ mtvare[ right ] ] ){
				se.erase( se.find( x ) ) ;
				mn = min( mn , x ) ;
				mx = max( mx , x ) ; 
			} 	
			l = min( mn , l ) ;
			r = max( mx , r ) ;			
		}
	 }
	 
	 
	 return ans ;
}



//   int main() {
//   	int n, s;
//   	assert(2 == scanf("%d %d", &n, &s));
//   	vector<int> p((unsigned) n);
//   	for(int i = 0; i < n; i++)
//   		assert(1 == scanf("%d", &p[(unsigned) i]));
//   	long long res = minimum_walk(p, s);
//   	printf("%lld\n", res);
//   	return 0;
//   }

Compilation message

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:80:7: warning: unused variable 'mx' [-Wunused-variable]
   80 |   int mx = 0 ;
      |       ^~

Subtask #1

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	47216 KB	Output is correct
2	Correct	25 ms	47188 KB	Output is correct
3	Correct	24 ms	47284 KB	Output is correct
4	Correct	24 ms	47188 KB	Output is correct
5	Correct	25 ms	47332 KB	Output is correct
6	Correct	25 ms	47288 KB	Output is correct
7	Correct	28 ms	47316 KB	Output is correct
8	Correct	25 ms	47204 KB	Output is correct
9	Correct	24 ms	47272 KB	Output is correct
10	Correct	25 ms	47204 KB	Output is correct
11	Correct	25 ms	47276 KB	Output is correct
12	Correct	29 ms	47280 KB	Output is correct
13	Correct	24 ms	47188 KB	Output is correct
14	Correct	26 ms	47288 KB	Output is correct
15	Correct	24 ms	47288 KB	Output is correct
16	Correct	24 ms	47200 KB	Output is correct
17	Correct	25 ms	47224 KB	Output is correct
18	Correct	25 ms	47188 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	47216 KB	Output is correct
2	Correct	25 ms	47188 KB	Output is correct
3	Correct	24 ms	47284 KB	Output is correct
4	Correct	24 ms	47188 KB	Output is correct
5	Correct	25 ms	47332 KB	Output is correct
6	Correct	25 ms	47288 KB	Output is correct
7	Correct	28 ms	47316 KB	Output is correct
8	Correct	25 ms	47204 KB	Output is correct
9	Correct	24 ms	47272 KB	Output is correct
10	Correct	25 ms	47204 KB	Output is correct
11	Correct	25 ms	47276 KB	Output is correct
12	Correct	29 ms	47280 KB	Output is correct
13	Correct	24 ms	47188 KB	Output is correct
14	Correct	26 ms	47288 KB	Output is correct
15	Correct	24 ms	47288 KB	Output is correct
16	Correct	24 ms	47200 KB	Output is correct
17	Correct	25 ms	47224 KB	Output is correct
18	Correct	25 ms	47188 KB	Output is correct
19	Correct	25 ms	47420 KB	Output is correct
20	Correct	25 ms	47316 KB	Output is correct
21	Correct	25 ms	47476 KB	Output is correct
22	Correct	25 ms	47456 KB	Output is correct
23	Correct	25 ms	47324 KB	Output is correct
24	Correct	25 ms	47456 KB	Output is correct
25	Correct	24 ms	47432 KB	Output is correct
26	Correct	30 ms	47328 KB	Output is correct
27	Correct	25 ms	47316 KB	Output is correct
28	Correct	26 ms	47360 KB	Output is correct
29	Correct	25 ms	47372 KB	Output is correct

Subtask #3

28.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	47216 KB	Output is correct
2	Correct	25 ms	47188 KB	Output is correct
3	Correct	24 ms	47284 KB	Output is correct
4	Correct	24 ms	47188 KB	Output is correct
5	Correct	25 ms	47332 KB	Output is correct
6	Correct	25 ms	47288 KB	Output is correct
7	Correct	28 ms	47316 KB	Output is correct
8	Correct	25 ms	47204 KB	Output is correct
9	Correct	24 ms	47272 KB	Output is correct
10	Correct	25 ms	47204 KB	Output is correct
11	Correct	25 ms	47276 KB	Output is correct
12	Correct	29 ms	47280 KB	Output is correct
13	Correct	24 ms	47188 KB	Output is correct
14	Correct	26 ms	47288 KB	Output is correct
15	Correct	24 ms	47288 KB	Output is correct
16	Correct	24 ms	47200 KB	Output is correct
17	Correct	25 ms	47224 KB	Output is correct
18	Correct	25 ms	47188 KB	Output is correct
19	Correct	25 ms	47420 KB	Output is correct
20	Correct	25 ms	47316 KB	Output is correct
21	Correct	25 ms	47476 KB	Output is correct
22	Correct	25 ms	47456 KB	Output is correct
23	Correct	25 ms	47324 KB	Output is correct
24	Correct	25 ms	47456 KB	Output is correct
25	Correct	24 ms	47432 KB	Output is correct
26	Correct	30 ms	47328 KB	Output is correct
27	Correct	25 ms	47316 KB	Output is correct
28	Correct	26 ms	47360 KB	Output is correct
29	Correct	25 ms	47372 KB	Output is correct
30	Correct	626 ms	170392 KB	Output is correct
31	Correct	764 ms	182740 KB	Output is correct
32	Correct	802 ms	245780 KB	Output is correct
33	Correct	592 ms	228832 KB	Output is correct
34	Correct	589 ms	228932 KB	Output is correct
35	Correct	609 ms	227808 KB	Output is correct
36	Correct	584 ms	206424 KB	Output is correct
37	Correct	614 ms	196360 KB	Output is correct
38	Correct	593 ms	195448 KB	Output is correct
39	Correct	598 ms	195392 KB	Output is correct
40	Correct	637 ms	197120 KB	Output is correct
41	Correct	760 ms	193300 KB	Output is correct
42	Correct	841 ms	205316 KB	Output is correct
43	Correct	811 ms	231608 KB	Output is correct

Subtask #4

0 / 20.0

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

Subtask #5

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	47216 KB	Output is correct
2	Correct	25 ms	47188 KB	Output is correct
3	Correct	24 ms	47284 KB	Output is correct
4	Correct	24 ms	47188 KB	Output is correct
5	Correct	25 ms	47332 KB	Output is correct
6	Correct	25 ms	47288 KB	Output is correct
7	Correct	28 ms	47316 KB	Output is correct
8	Correct	25 ms	47204 KB	Output is correct
9	Correct	24 ms	47272 KB	Output is correct
10	Correct	25 ms	47204 KB	Output is correct
11	Correct	25 ms	47276 KB	Output is correct
12	Correct	29 ms	47280 KB	Output is correct
13	Correct	24 ms	47188 KB	Output is correct
14	Correct	26 ms	47288 KB	Output is correct
15	Correct	24 ms	47288 KB	Output is correct
16	Correct	24 ms	47200 KB	Output is correct
17	Correct	25 ms	47224 KB	Output is correct
18	Correct	25 ms	47188 KB	Output is correct
19	Correct	25 ms	47420 KB	Output is correct
20	Correct	25 ms	47316 KB	Output is correct
21	Correct	25 ms	47476 KB	Output is correct
22	Correct	25 ms	47456 KB	Output is correct
23	Correct	25 ms	47324 KB	Output is correct
24	Correct	25 ms	47456 KB	Output is correct
25	Correct	24 ms	47432 KB	Output is correct
26	Correct	30 ms	47328 KB	Output is correct
27	Correct	25 ms	47316 KB	Output is correct
28	Correct	26 ms	47360 KB	Output is correct
29	Correct	25 ms	47372 KB	Output is correct
30	Correct	626 ms	170392 KB	Output is correct
31	Correct	764 ms	182740 KB	Output is correct
32	Correct	802 ms	245780 KB	Output is correct
33	Correct	592 ms	228832 KB	Output is correct
34	Correct	589 ms	228932 KB	Output is correct
35	Correct	609 ms	227808 KB	Output is correct
36	Correct	584 ms	206424 KB	Output is correct
37	Correct	614 ms	196360 KB	Output is correct
38	Correct	593 ms	195448 KB	Output is correct
39	Correct	598 ms	195392 KB	Output is correct
40	Correct	637 ms	197120 KB	Output is correct
41	Correct	760 ms	193300 KB	Output is correct
42	Correct	841 ms	205316 KB	Output is correct
43	Correct	811 ms	231608 KB	Output is correct
44	Incorrect	26 ms	47464 KB	3rd lines differ - on the 1st token, expected: '3304', found: '3506'
45	Halted	0 ms	0 KB	-