oj.uz

Submission #1105062

# Submission time Handle Problem Language Result Execution time Memory
1105062 2024-10-25T09:08:38 Z alexander707070 Ancient Books (IOI17_books) C++14
Compilation error
 0 ms 0 KB 
Submission #1105058
#	Submission timeUTC+3	Handle	Problem	Language	Result	Execution time	Memory
1105058	2024-10-25 12:04:59	alexander707070	Ancient Books (IOI17_books)	C++14	
50 / 100
106 ms	29440 KB
books
#include<bits/stdc++.h>
#define MAXN 1000007
using namespace std;
 
int n,s,p[MAXN],fr,last,mins,maxs,pref[MAXN],curr;
bool li[MAXN];
long long ans;
 
int k,cycle[MAXN];
pair<int,int> where[MAXN];
 
void dfs(int x){
	li[x]=true;
	cycle[x]=k;
 
	ans+=abs(x-p[x]);
	mins=min(mins,x);
	maxs=max(maxs,x);
 
	if(!li[p[x]])dfs(p[x]);
}
 
int dp[1007][1007];
bool vis[1007][1007];
 
int ff(int l,int r){
	if(l<=1 and r>=n)return 0;
	
	if(vis[l][r])return dp[l][r];
	vis[l][r]=true;
	dp[l][r]=2*n;
 
	if(l>1){
		int from=l-1,to=r,ll=l-1,rr=r+1;
		while(ll>=from or rr<=to){
			while(ll>=from){
				from=min(from,where[cycle[ll]].first);
				to=max(to,where[cycle[ll]].second);
				ll--;
			}
 
			while(rr<=to){
				from=min(from,where[cycle[rr]].first);
				to=max(to,where[cycle[rr]].second);
				rr++;
			}
		}
 
		dp[l][r]=min(dp[l][r],ff(from,to)+2);
	}
 
	if(r<n){
		int from=l,to=r+1,ll=l-1,rr=r+1;
		while(ll>=from or rr<=to){
			while(ll>=from){
				from=min(from,where[cycle[ll]].first);
				to=max(to,where[cycle[ll]].second);
				ll--;
			}
 
			while(rr<=to){
				from=min(from,where[cycle[rr]].first);
				to=max(to,where[cycle[rr]].second);
				rr++;
			}
		}
 
		dp[l][r]=min(dp[l][r],ff(from,to)+2);
	}
 
	return dp[l][r];
}
 
long long minimum_walk(vector<int> P, int S){
	n=int(P.size()); s=S+1;
 
	for(int i=1;i<=n;i++){
		p[i]=P[i-1]+1;
		li[i]=false; pref[i]=0;
	}
	last=0; fr=n+1; k=0; ans=0;
 
	for(int i=1;i<=n;i++){
		if(!li[i]){
			if(p[i]!=i)last=i;
			dfs(i);
		}
	}
 
	for(int i=1;i<=n;i++)li[i]=false;
 
	for(int i=n;i>=1;i--){
		if(!li[i]){
			k++;
			if(p[i]!=i)fr=i;
 
			mins=n; maxs=1;
			dfs(i);
 
			where[k]={mins,maxs};
			pref[mins]++; pref[maxs]--;
		}
	}
	ans/=2;
 
	/// more steps inside initial cycle
 
	if(s!=1){
      int from=s,to=s,ll=s,rr=s;
		while(ll>=from or rr<=to){
			while(ll>=from){
				from=min(from,where[cycle[ll]].first);
				to=max(to,where[cycle[ll]].second);
				ll--;
			}
 
			while(rr<=to){
				from=min(from,where[cycle[rr]].first);
				to=max(to,where[cycle[rr]].second);
				rr++;
			}
		}
      ans+=ff(from,to);
    }else{
		for(int i=1;i<=n-1;i++){
			curr+=pref[i];
			if(i<s)continue;
	
			if(curr==0 and last>i)ans+=2;
		}
	
		curr=0;
		for(int i=n;i>=2;i--){
			curr+=pref[i];
			if(i>s)continue;
	
			if(curr==0 and fr<i)ans+=2;
		}
	}
	
	return ans;
}
 
/*int main(){
 
	vector<int> perm;
	for(int i=0;i<10;i++){
		perm.push_back(i);
	}
 
	while(true){
		random_shuffle(perm.begin(),perm.end());
		for(int i=0;i<10;i++){
			cout<<perm[i]<<" ";
		}
		cout<<"\n";
 
		int z=rand()%10;
 
		cout<<z<<"\n";
		minimum_walk(perm,z);
	}
 
	return 0;
}*/

Compilation message

books.cpp:2:12: error: stray '#' in program
    2 | Submission #1105058
      |            ^
books.cpp:3:3: error: invalid preprocessing directive #Submission
    3 | # Submission timeUTC+3 Handle Problem Language Result Execution time Memory
      |   ^~~~~~~~~~
books.cpp:2:1: error: 'Submission' does not name a type
    2 | Submission #1105058
      | ^~~~~~~~~~
In file included from /usr/include/c++/10/cmath:43,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from books.cpp:8:
/usr/include/c++/10/ext/type_traits.h:162:35: error: 'bool __gnu_cxx::__is_null_pointer' redeclared as different kind of entity
  162 |   __is_null_pointer(std::nullptr_t)
      |                                   ^
/usr/include/c++/10/ext/type_traits.h:157:5: note: previous declaration 'template<class _Type> bool __gnu_cxx::__is_null_pointer(_Type)'
  157 |     __is_null_pointer(_Type)
      |     ^~~~~~~~~~~~~~~~~
/usr/include/c++/10/ext/type_traits.h:162:26: error: 'nullptr_t' is not a member of 'std'
  162 |   __is_null_pointer(std::nullptr_t)
      |                          ^~~~~~~~~
In file included from /usr/include/c++/10/bits/exception_ptr.h:40,
                 from /usr/include/c++/10/exception:147,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from books.cpp:8:
/usr/include/c++/10/new:126:26: error: declaration of 'operator new' as non-function
  126 | _GLIBCXX_NODISCARD void* operator new(std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                          ^~~~~~~~
/usr/include/c++/10/new:126:44: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
  126 | _GLIBCXX_NODISCARD void* operator new(std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                                            ^~~~~~
In file included from /usr/include/stdlib.h:31,
                 from /usr/include/c++/10/bits/std_abs.h:38,
                 from /usr/include/c++/10/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from books.cpp:8:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/10/bits/exception_ptr.h:40,
                 from /usr/include/c++/10/exception:147,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from books.cpp:8:
/usr/include/c++/10/new:127:41: error: attributes after parenthesized initializer ignored [-fpermissive]
  127 |   __attribute__((__externally_visible__));
      |                                         ^
/usr/include/c++/10/new:128:26: error: declaration of 'operator new []' as non-function
  128 | _GLIBCXX_NODISCARD void* operator new[](std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                          ^~~~~~~~
/usr/include/c++/10/new:128:46: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
  128 | _GLIBCXX_NODISCARD void* operator new[](std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                                              ^~~~~~
In file included from /usr/include/stdlib.h:31,
                 from /usr/include/c++/10/bits/std_abs.h:38,
                 from /usr/include/c++/10/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from books.cpp:8:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/10/bits/exception_ptr.h:40,
                 from /usr/include/c++/10/exception:147,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from books.cpp:8:
/usr/include/c++/10/new:129:41: error: attributes after parenthesized initializer ignored [-fpermissive]
  129 |   __attribute__((__externally_visible__));
      |                                         ^
/usr/include/c++/10/new:135:34: error: 'std::size_t' has not been declared
  135 | void operator delete(void*, std::size_t) _GLIBCXX_USE_NOEXCEPT
      |                                  ^~~~~~
/usr/include/c++/10/new:137:36: error: 'std::size_t' has not been declared
  137 | void operator delete[](void*, std::size_t) _GLIBCXX_USE_NOEXCEPT
      |                                    ^~~~~~
/usr/include/c++/10/new:140:26: error: declaration of 'operator new' as non-function
  140 | _GLIBCXX_NODISCARD void* operator new(std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
      |                          ^~~~~~~~
/usr/include/c++/10/new:140:44: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
  140 | _GLIBCXX_NODISCARD void* operator new(std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
      |                                            ^~~~~~
In file included from /usr/include/stdlib.h:31,
                 from /usr/include/c++/10/bits/std_abs.h:38,
                 from /usr/include/c++/10/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from books.cpp:8:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/10/bits/exception_ptr.h:40,
                 from /usr/include/c++/10/exception:147,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from books.cpp:8:
/usr/include/c++/10/new:140:52: error: expected primary-expression before 'const'
  140 | _GLIBCXX_NODISCARD void* operator new(std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
      |                                                    ^~~~~
/usr/include/c++/10/new:142:26: error: declaration of 'operator new []' as non-function
  142 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
      |                          ^~~~~~~~
/usr/include/c++/10/new:142:46: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
  142 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
      |                                              ^~~~~~
In file included from /usr/include/stdlib.h:31,
                 from /usr/include/c++/10/bits/std_abs.h:38,
                 from /usr/include/c++/10/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from books.cpp:8:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/10/bits/exception_ptr.h:40,
                 from /usr/include/c++/10/exception:147,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from books.cpp:8:
/usr/include/c++/10/new:142:54: error: expected primary-expression before 'const'
  142 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
      |                                                      ^~~~~
/usr/include/c++/10/new:174:33: error: declaration of 'operator new' as non-function
  174 | _GLIBCXX_NODISCARD inline void* operator new(std::size_t, void* __p) _GLIBCXX_USE_NOEXCEPT
      |                                 ^~~~~~~~
/usr/include/c++/10/new:174:51: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
  174 | _GLIBCXX_NODISCARD inline void* operator new(std::size_t, void* __p) _GLIBCXX_USE_NOEXCEPT
      |                                                   ^~~~~~
In file included from /usr/include/stdlib.h:31,
                 from /usr/include/c++/10/bits/std_abs.h:38,
                 from /usr/include/c++/10/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from books.cpp:8:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/10/bits/exception_ptr.h:40,
                 from /usr/include/c++/10/exception:147,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from books.cpp:8:
/usr/include/c++/10/new:174:59: error: expected primary-expression before 'void'
  174 | _GLIBCXX_NODISCARD inline void* operator new(std::size_t, void* __p) _GLIBCXX_USE_NOEXCEPT
      |                                                           ^~~~
/usr/include/c++/10/new:176:33: error: declaration of 'operator new []' as non-function
  176 | _GLIBCXX_NODISCARD inline void* operator new[](std::size_t, void* __p) _GLIBCXX_USE_NOEXCEPT
      |                                 ^~~~~~~~
/usr/include/c++/10/new:176:53: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
  176 | _GLIBCXX_NODISCARD inline void* operator new[](std::size_t, void* __p) _GLIBCXX_USE_NOEXCEPT
      |                                                     ^~~~~~
In file included from /usr/include/stdlib.h:31,
                 from /usr/include/c++/10/bits/std_abs.h:38,
                 from /usr/include/c++/10/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from books.cpp:8:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/10/bits/exception_ptr.h:40,
                 from /usr/include/c++/10/exception:147,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from books.cpp:8:
/usr/include/c++/10/new:176:61: error: expected primary-expression before 'void'
  176 | _GLIBCXX_NODISCARD inline void* operator new[](std::size_t, void* __p) _GLIBCXX_USE_NOEXCEPT
      |                                                             ^~~~
In file included from /usr/include/c++/10/bits/move.h:57,
                 from /usr/include/c++/10/bits/nested_exception.h:40,
                 from /usr/include/c++/10/exception:148,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from books.cpp:8:
/usr/include/c++/10/type_traits:402:31: error: 'std::size_t' has not been declared
  402 |   template<typename _Tp, std::size_t _Size>
      |                               ^~~~~~
/usr/include/c++/10/type_traits:403:25: error: '_Size' was not declared in this scope
  403 |     struct is_array<_Tp[_Size]>
      |                         ^~~~~
/usr/include/c++/10/type_traits:403:31: error: template argument 1 is invalid
  403 |     struct is_array<_Tp[_Size]>
      |                               ^
/usr/include/c++/10/type_traits:508:42: error: 'nullptr_t' is not a member of 'std'; did you mean 'nullptr_t'?
  508 |     struct __is_null_pointer_helper<std::nullptr_t>
      |                                          ^~~~~~~~~
In file included from /usr/include/c++/10/cstddef:50,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:45,
                 from books.cpp:8:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:433:29: note: 'nullptr_t' declared here
  433 |   typedef decltype(nullptr) nullptr_t;
      |                             ^~~~~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
                 from /usr/include/c++/10/bits/nested_exception.h:40,
                 from /usr/include/c++/10/exception:148,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from books.cpp:8:
/usr/include/c++/10/type_traits:508:42: error: 'nullptr_t' is not a member of 'std'; did you mean 'nullptr_t'?
  508 |     struct __is_null_pointer_helper<std::nullptr_t>
      |                                          ^~~~~~~~~
In file included from /usr/include/c++/10/cstddef:50,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:45,
                 from books.cpp:8:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:433:29: note: 'nullptr_t' declared here
  433 |   typedef decltype(nullptr) nullptr_t;
      |                             ^~~~~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
                 from /usr/include/c++/10/bits/nested_exception.h:40,
                 from /usr/include/c++/10/exception:148,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from books.cpp:8:
/usr/include/c++/10/type_traits:508:51: error: template argument 1 is invalid
  508 |     struct __is_null_pointer_helper<std::nullptr_t>
      |                                                   ^
/usr/include/c++/10/type_traits:1351:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1351 |     : public integral_constant<std::size_t, alignof(_Tp)>
      |                                     ^~~~~~
In file included from /usr/include/stdlib.h:31,
                 from /usr/include/c++/10/bits/std_abs.h:38,
                 from /usr/include/c++/10/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from books.cpp:8:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
                 from /usr/include/c++/10/bits/nested_exception.h:40,
                 from /usr/include/c++/10/exception:148,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from books.cpp:8:
/usr/include/c++/10/type_traits:1351:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1351 |     : public integral_constant<std::size_t, alignof(_Tp)>
      |                                     ^~~~~~
In file included from /usr/include/stdlib.h:31,
                 from /usr/include/c++/10/bits/std_abs.h:38,
                 from /usr/include/c++/10/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from books.cpp:8:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
                 from /usr/include/c++/10/bits/nested_exception.h:40,
                 from /usr/include/c++/10/exception:148,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from books.cpp:8:
/usr/include/c++/10/type_traits:1351:57: error: template argument 1 is invalid
 1351 |     : public integral_constant<std::size_t, alignof(_Tp)>
      |                                                         ^
/usr/include/c++/10/type_traits:1351:57: note: invalid template non-type parameter
/usr/include/c++/10/type_traits:1360:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1360 |     : public integral_constant<std::size_t, 0> { };
      |                                     ^~~~~~
In file included from /usr/include/stdlib.h:31,
                 from /usr/include/c++/10/bits/std_abs.h:38,
                 from /usr/include/c++/10/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from books.cpp:8:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
                 from /usr/include/c++/10/bits/nested_exception.h:40,
                 from /usr/include/c++/10/exception:148,
                 from /usr/include/c++/1