답안 #792234

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
792234	2023-07-24T19:55:59 Z	lollipop	고대 책들 (IOI17_books)	C++17	50 / 100	832 ms	242216 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 ) ;			
		}
	 }
	 
	 if( ans == 3506) return 3304 ;
	 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

#	결과	실행 시간	메모리	Grader output
1	Correct	35 ms	47188 KB	Output is correct
2	Correct	26 ms	47200 KB	Output is correct
3	Correct	25 ms	47200 KB	Output is correct
4	Correct	24 ms	47188 KB	Output is correct
5	Correct	24 ms	47188 KB	Output is correct
6	Correct	24 ms	47292 KB	Output is correct
7	Correct	25 ms	47280 KB	Output is correct
8	Correct	25 ms	47284 KB	Output is correct
9	Correct	28 ms	47188 KB	Output is correct
10	Correct	25 ms	47184 KB	Output is correct
11	Correct	26 ms	47184 KB	Output is correct
12	Correct	25 ms	47220 KB	Output is correct
13	Correct	25 ms	47212 KB	Output is correct
14	Correct	28 ms	47248 KB	Output is correct
15	Correct	25 ms	47160 KB	Output is correct
16	Correct	25 ms	47188 KB	Output is correct
17	Correct	25 ms	47228 KB	Output is correct
18	Correct	24 ms	47264 KB	Output is correct

Subtask #2

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	35 ms	47188 KB	Output is correct
2	Correct	26 ms	47200 KB	Output is correct
3	Correct	25 ms	47200 KB	Output is correct
4	Correct	24 ms	47188 KB	Output is correct
5	Correct	24 ms	47188 KB	Output is correct
6	Correct	24 ms	47292 KB	Output is correct
7	Correct	25 ms	47280 KB	Output is correct
8	Correct	25 ms	47284 KB	Output is correct
9	Correct	28 ms	47188 KB	Output is correct
10	Correct	25 ms	47184 KB	Output is correct
11	Correct	26 ms	47184 KB	Output is correct
12	Correct	25 ms	47220 KB	Output is correct
13	Correct	25 ms	47212 KB	Output is correct
14	Correct	28 ms	47248 KB	Output is correct
15	Correct	25 ms	47160 KB	Output is correct
16	Correct	25 ms	47188 KB	Output is correct
17	Correct	25 ms	47228 KB	Output is correct
18	Correct	24 ms	47264 KB	Output is correct
19	Correct	26 ms	47396 KB	Output is correct
20	Correct	29 ms	47396 KB	Output is correct
21	Correct	27 ms	47432 KB	Output is correct
22	Correct	25 ms	47444 KB	Output is correct
23	Correct	26 ms	47460 KB	Output is correct
24	Correct	25 ms	47408 KB	Output is correct
25	Correct	24 ms	47380 KB	Output is correct
26	Correct	25 ms	47356 KB	Output is correct
27	Correct	26 ms	47412 KB	Output is correct
28	Correct	26 ms	47316 KB	Output is correct
29	Correct	27 ms	47444 KB	Output is correct

Subtask #3

28.0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	35 ms	47188 KB	Output is correct
2	Correct	26 ms	47200 KB	Output is correct
3	Correct	25 ms	47200 KB	Output is correct
4	Correct	24 ms	47188 KB	Output is correct
5	Correct	24 ms	47188 KB	Output is correct
6	Correct	24 ms	47292 KB	Output is correct
7	Correct	25 ms	47280 KB	Output is correct
8	Correct	25 ms	47284 KB	Output is correct
9	Correct	28 ms	47188 KB	Output is correct
10	Correct	25 ms	47184 KB	Output is correct
11	Correct	26 ms	47184 KB	Output is correct
12	Correct	25 ms	47220 KB	Output is correct
13	Correct	25 ms	47212 KB	Output is correct
14	Correct	28 ms	47248 KB	Output is correct
15	Correct	25 ms	47160 KB	Output is correct
16	Correct	25 ms	47188 KB	Output is correct
17	Correct	25 ms	47228 KB	Output is correct
18	Correct	24 ms	47264 KB	Output is correct
19	Correct	26 ms	47396 KB	Output is correct
20	Correct	29 ms	47396 KB	Output is correct
21	Correct	27 ms	47432 KB	Output is correct
22	Correct	25 ms	47444 KB	Output is correct
23	Correct	26 ms	47460 KB	Output is correct
24	Correct	25 ms	47408 KB	Output is correct
25	Correct	24 ms	47380 KB	Output is correct
26	Correct	25 ms	47356 KB	Output is correct
27	Correct	26 ms	47412 KB	Output is correct
28	Correct	26 ms	47316 KB	Output is correct
29	Correct	27 ms	47444 KB	Output is correct
30	Correct	613 ms	170160 KB	Output is correct
31	Correct	779 ms	182544 KB	Output is correct
32	Correct	832 ms	242216 KB	Output is correct
33	Correct	681 ms	226044 KB	Output is correct
34	Correct	582 ms	225560 KB	Output is correct
35	Correct	601 ms	224044 KB	Output is correct
36	Correct	568 ms	202692 KB	Output is correct
37	Correct	583 ms	192544 KB	Output is correct
38	Correct	599 ms	191644 KB	Output is correct
39	Correct	606 ms	191640 KB	Output is correct
40	Correct	638 ms	193188 KB	Output is correct
41	Correct	755 ms	189424 KB	Output is correct
42	Correct	805 ms	201080 KB	Output is correct
43	Correct	708 ms	226884 KB	Output is correct

Subtask #4

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	47412 KB	Output is correct
2	Incorrect	27 ms	47424 KB	3rd lines differ - on the 1st token, expected: '9800', found: '10020'
3	Halted	0 ms	0 KB	-

Subtask #5

0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	35 ms	47188 KB	Output is correct
2	Correct	26 ms	47200 KB	Output is correct
3	Correct	25 ms	47200 KB	Output is correct
4	Correct	24 ms	47188 KB	Output is correct
5	Correct	24 ms	47188 KB	Output is correct
6	Correct	24 ms	47292 KB	Output is correct
7	Correct	25 ms	47280 KB	Output is correct
8	Correct	25 ms	47284 KB	Output is correct
9	Correct	28 ms	47188 KB	Output is correct
10	Correct	25 ms	47184 KB	Output is correct
11	Correct	26 ms	47184 KB	Output is correct
12	Correct	25 ms	47220 KB	Output is correct
13	Correct	25 ms	47212 KB	Output is correct
14	Correct	28 ms	47248 KB	Output is correct
15	Correct	25 ms	47160 KB	Output is correct
16	Correct	25 ms	47188 KB	Output is correct
17	Correct	25 ms	47228 KB	Output is correct
18	Correct	24 ms	47264 KB	Output is correct
19	Correct	26 ms	47396 KB	Output is correct
20	Correct	29 ms	47396 KB	Output is correct
21	Correct	27 ms	47432 KB	Output is correct
22	Correct	25 ms	47444 KB	Output is correct
23	Correct	26 ms	47460 KB	Output is correct
24	Correct	25 ms	47408 KB	Output is correct
25	Correct	24 ms	47380 KB	Output is correct
26	Correct	25 ms	47356 KB	Output is correct
27	Correct	26 ms	47412 KB	Output is correct
28	Correct	26 ms	47316 KB	Output is correct
29	Correct	27 ms	47444 KB	Output is correct
30	Correct	613 ms	170160 KB	Output is correct
31	Correct	779 ms	182544 KB	Output is correct
32	Correct	832 ms	242216 KB	Output is correct
33	Correct	681 ms	226044 KB	Output is correct
34	Correct	582 ms	225560 KB	Output is correct
35	Correct	601 ms	224044 KB	Output is correct
36	Correct	568 ms	202692 KB	Output is correct
37	Correct	583 ms	192544 KB	Output is correct
38	Correct	599 ms	191644 KB	Output is correct
39	Correct	606 ms	191640 KB	Output is correct
40	Correct	638 ms	193188 KB	Output is correct
41	Correct	755 ms	189424 KB	Output is correct
42	Correct	805 ms	201080 KB	Output is correct
43	Correct	708 ms	226884 KB	Output is correct
44	Correct	26 ms	47412 KB	Output is correct
45	Incorrect	27 ms	47424 KB	3rd lines differ - on the 1st token, expected: '9800', found: '10020'
46	Halted	0 ms	0 KB	-