Submission #792239

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
792239	2023-07-24T20:10:47 Z	lollipop	Ancient Books (IOI17_books)	C++17	50 / 100	797 ms	245720 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 ] = vvv.size() , 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 + 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{
			int xx = 0 ;
			if( right > r ) xx = 2 ; 
	 	    ans = ans + xx ; 
	 	    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	23 ms	47284 KB	Output is correct
2	Correct	23 ms	47268 KB	Output is correct
3	Correct	23 ms	47276 KB	Output is correct
4	Correct	23 ms	47264 KB	Output is correct
5	Correct	23 ms	47268 KB	Output is correct
6	Correct	23 ms	47180 KB	Output is correct
7	Correct	23 ms	47196 KB	Output is correct
8	Correct	24 ms	47188 KB	Output is correct
9	Correct	25 ms	47280 KB	Output is correct
10	Correct	24 ms	47336 KB	Output is correct
11	Correct	23 ms	47184 KB	Output is correct
12	Correct	23 ms	47260 KB	Output is correct
13	Correct	24 ms	47200 KB	Output is correct
14	Correct	26 ms	47220 KB	Output is correct
15	Correct	24 ms	47224 KB	Output is correct
16	Correct	23 ms	47160 KB	Output is correct
17	Correct	24 ms	47188 KB	Output is correct
18	Correct	23 ms	47188 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	47284 KB	Output is correct
2	Correct	23 ms	47268 KB	Output is correct
3	Correct	23 ms	47276 KB	Output is correct
4	Correct	23 ms	47264 KB	Output is correct
5	Correct	23 ms	47268 KB	Output is correct
6	Correct	23 ms	47180 KB	Output is correct
7	Correct	23 ms	47196 KB	Output is correct
8	Correct	24 ms	47188 KB	Output is correct
9	Correct	25 ms	47280 KB	Output is correct
10	Correct	24 ms	47336 KB	Output is correct
11	Correct	23 ms	47184 KB	Output is correct
12	Correct	23 ms	47260 KB	Output is correct
13	Correct	24 ms	47200 KB	Output is correct
14	Correct	26 ms	47220 KB	Output is correct
15	Correct	24 ms	47224 KB	Output is correct
16	Correct	23 ms	47160 KB	Output is correct
17	Correct	24 ms	47188 KB	Output is correct
18	Correct	23 ms	47188 KB	Output is correct
19	Correct	24 ms	47316 KB	Output is correct
20	Correct	24 ms	47316 KB	Output is correct
21	Correct	25 ms	47400 KB	Output is correct
22	Correct	27 ms	47416 KB	Output is correct
23	Correct	29 ms	47464 KB	Output is correct
24	Correct	23 ms	47428 KB	Output is correct
25	Correct	24 ms	47444 KB	Output is correct
26	Correct	25 ms	47332 KB	Output is correct
27	Correct	24 ms	47384 KB	Output is correct
28	Correct	24 ms	47412 KB	Output is correct
29	Correct	24 ms	47444 KB	Output is correct

Subtask #3

28.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	47284 KB	Output is correct
2	Correct	23 ms	47268 KB	Output is correct
3	Correct	23 ms	47276 KB	Output is correct
4	Correct	23 ms	47264 KB	Output is correct
5	Correct	23 ms	47268 KB	Output is correct
6	Correct	23 ms	47180 KB	Output is correct
7	Correct	23 ms	47196 KB	Output is correct
8	Correct	24 ms	47188 KB	Output is correct
9	Correct	25 ms	47280 KB	Output is correct
10	Correct	24 ms	47336 KB	Output is correct
11	Correct	23 ms	47184 KB	Output is correct
12	Correct	23 ms	47260 KB	Output is correct
13	Correct	24 ms	47200 KB	Output is correct
14	Correct	26 ms	47220 KB	Output is correct
15	Correct	24 ms	47224 KB	Output is correct
16	Correct	23 ms	47160 KB	Output is correct
17	Correct	24 ms	47188 KB	Output is correct
18	Correct	23 ms	47188 KB	Output is correct
19	Correct	24 ms	47316 KB	Output is correct
20	Correct	24 ms	47316 KB	Output is correct
21	Correct	25 ms	47400 KB	Output is correct
22	Correct	27 ms	47416 KB	Output is correct
23	Correct	29 ms	47464 KB	Output is correct
24	Correct	23 ms	47428 KB	Output is correct
25	Correct	24 ms	47444 KB	Output is correct
26	Correct	25 ms	47332 KB	Output is correct
27	Correct	24 ms	47384 KB	Output is correct
28	Correct	24 ms	47412 KB	Output is correct
29	Correct	24 ms	47444 KB	Output is correct
30	Correct	603 ms	167804 KB	Output is correct
31	Correct	762 ms	180184 KB	Output is correct
32	Correct	797 ms	245720 KB	Output is correct
33	Correct	579 ms	228928 KB	Output is correct
34	Correct	562 ms	229020 KB	Output is correct
35	Correct	558 ms	227788 KB	Output is correct
36	Correct	544 ms	206416 KB	Output is correct
37	Correct	561 ms	196328 KB	Output is correct
38	Correct	584 ms	195468 KB	Output is correct
39	Correct	590 ms	195452 KB	Output is correct
40	Correct	627 ms	196996 KB	Output is correct
41	Correct	742 ms	193468 KB	Output is correct
42	Correct	783 ms	205284 KB	Output is correct
43	Correct	736 ms	230976 KB	Output is correct

Subtask #4

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	23 ms	47404 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	23 ms	47284 KB	Output is correct
2	Correct	23 ms	47268 KB	Output is correct
3	Correct	23 ms	47276 KB	Output is correct
4	Correct	23 ms	47264 KB	Output is correct
5	Correct	23 ms	47268 KB	Output is correct
6	Correct	23 ms	47180 KB	Output is correct
7	Correct	23 ms	47196 KB	Output is correct
8	Correct	24 ms	47188 KB	Output is correct
9	Correct	25 ms	47280 KB	Output is correct
10	Correct	24 ms	47336 KB	Output is correct
11	Correct	23 ms	47184 KB	Output is correct
12	Correct	23 ms	47260 KB	Output is correct
13	Correct	24 ms	47200 KB	Output is correct
14	Correct	26 ms	47220 KB	Output is correct
15	Correct	24 ms	47224 KB	Output is correct
16	Correct	23 ms	47160 KB	Output is correct
17	Correct	24 ms	47188 KB	Output is correct
18	Correct	23 ms	47188 KB	Output is correct
19	Correct	24 ms	47316 KB	Output is correct
20	Correct	24 ms	47316 KB	Output is correct
21	Correct	25 ms	47400 KB	Output is correct
22	Correct	27 ms	47416 KB	Output is correct
23	Correct	29 ms	47464 KB	Output is correct
24	Correct	23 ms	47428 KB	Output is correct
25	Correct	24 ms	47444 KB	Output is correct
26	Correct	25 ms	47332 KB	Output is correct
27	Correct	24 ms	47384 KB	Output is correct
28	Correct	24 ms	47412 KB	Output is correct
29	Correct	24 ms	47444 KB	Output is correct
30	Correct	603 ms	167804 KB	Output is correct
31	Correct	762 ms	180184 KB	Output is correct
32	Correct	797 ms	245720 KB	Output is correct
33	Correct	579 ms	228928 KB	Output is correct
34	Correct	562 ms	229020 KB	Output is correct
35	Correct	558 ms	227788 KB	Output is correct
36	Correct	544 ms	206416 KB	Output is correct
37	Correct	561 ms	196328 KB	Output is correct
38	Correct	584 ms	195468 KB	Output is correct
39	Correct	590 ms	195452 KB	Output is correct
40	Correct	627 ms	196996 KB	Output is correct
41	Correct	742 ms	193468 KB	Output is correct
42	Correct	783 ms	205284 KB	Output is correct
43	Correct	736 ms	230976 KB	Output is correct
44	Incorrect	23 ms	47404 KB	3rd lines differ - on the 1st token, expected: '3304', found: '3506'
45	Halted	0 ms	0 KB	-