oj.uz

Submission #199379

# Submission time Handle Problem Language Result Execution time Memory
199379 2020-01-31T21:06:06 Z kimbj0709 Pancake (NOI12_pancake) C++17
25 / 25
 940 ms 23944 KB 
#include <bits/stdc++.h>
using namespace std;
vector<int> tar;
map<vector<int>,int> map1[10];
int recursive(int d,vector<int> vect1){
  if(d>vect1.size()+1){
    return INT_MAX;
  }
  if(map1[d].find(vect1)!=map1[d].end()){
    return map1[d][vect1];
  }
  for(int i=1;i<vect1.size();i++){
    if(vect1[i]<vect1[i-1]){
    }
    else{
      goto cont;
    }
  }
  return d;
  cont : ;
  int ret = INT_MAX;
  for(int i=0;i<vect1.size();i++){
      reverse(vect1.begin()+i,vect1.end());
      ret = min(ret,recursive(d+1,vect1));
      reverse(vect1.begin()+i,vect1.end());
    }
  map1[d][vect1] = ret;
  return map1[d][vect1];
}
void find(){
  int no_of_input;
  int input;
  vector<int> vect1;
  cin >> no_of_input;
  vector<int> vect2;
  for(int i=0;i<no_of_input;i++){
    cin >> input;
    vect1.push_back(input);
    vect2.push_back(input);
  }
  sort(vect2.begin(),vect2.end());
  for(int i=0;i<vect1.size();i++){
    for(int j=0;j<vect2.size();j++){
      if(vect1[i]==vect2[j]){
        vect1[i] = j;
        break;
      }
    }
  }
  cout << recursive(0,vect1) << "\n";
  return;
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);cout.tie(0);
  int no_of_input;
  cin >> no_of_input;
  for(int i=0;i<no_of_input;i++){
    find();
  }
}

Compilation message

pancake.cpp: In function 'int recursive(int, std::vector<int>)':
pancake.cpp:6:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(d>vect1.size()+1){
      ~^~~~~~~~~~~~~~~
pancake.cpp:12:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=1;i<vect1.size();i++){
               ~^~~~~~~~~~~~~
pancake.cpp:22:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<vect1.size();i++){
               ~^~~~~~~~~~~~~
pancake.cpp: In function 'void find()':
pancake.cpp:42:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<vect1.size();i++){
               ~^~~~~~~~~~~~~
pancake.cpp:43:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<vect2.size();j++){
                 ~^~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 767 ms 19576 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 869 ms 21384 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 851 ms 21240 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 764 ms 19576 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 940 ms 23944 KB Output is correct