Submission #731766

#TimeUsernameProblemLanguageResultExecution timeMemory
731766TrunktyPancake (NOI12_pancake)C++14
25 / 25
169 ms11860 KiB
#include <bits/extc++.h> using namespace std; typedef long long ll; #define int ll int t; map<vector<int>,int> best; int arr[9]; signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); for(int i=1;i<=8;i++){ vector<int> v; for(int j=i;j>=1;j--){ v.push_back(j); } best[v] = 1; vector<vector<int>> bfs = {v}; for(int j=0;j<bfs.size();j++){ vector<int> x = bfs[j]; for(int k=0;k<i-1;k++){ reverse(x.begin()+k,x.begin()+i); if(!best[x]){ best[x] = best[bfs[j]]+1; bfs.push_back(x); } reverse(x.begin()+k,x.begin()+i); } } } cin >> t; for(int e=1;e<=t;e++){ int n; cin >> n; vector<int> v; map<int,int> mp; for(int i=1;i<=n;i++){ cin >> arr[i]; v.push_back(arr[i]); } sort(v.begin(),v.end()); for(int i=0;i<v.size();i++){ mp[v[i]] = i+1; } vector<int> v2; for(int i=1;i<=n;i++){ v2.push_back(mp[arr[i]]); } cout << best[v2]-1LL << "\n"; } return 0; }

Compilation message (stderr)

pancake.cpp: In function 'int main()':
pancake.cpp:20:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         for(int j=0;j<bfs.size();j++){
      |                     ~^~~~~~~~~~~
pancake.cpp:43:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         for(int i=0;i<v.size();i++){
      |                     ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...