oj.uz

Submission #367697

# Submission time Handle Problem Language Result Execution time Memory
367697 2021-02-18T03:29:09 Z david0506 Pancake (NOI12_pancake) C++14
20 / 25
 1000 ms 2668 KB 
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <map>

using namespace std;

int n, k;

int BFS(string s, string ans)
{
    queue< pair<string, pair<int, int> > > q;
    q.push({ s, {0, -1} });
    map<string, bool> mp;
    while(!q.empty()){
        string x=q.front().first; int cnt=q.front().second.first, prv=q.front().second.second;
        q.pop();
        if(x==ans){ return cnt; }
        if(mp.count(x)){ continue; }
        mp[x]=1;
        for(int i=0; i<n-1; i++){
            if(i==prv){ continue; }
            string sub=x.substr(i, x.size());
            reverse(sub.begin(), sub.end());
            string nxt=x.substr(0, i)+sub;
            if(mp.count(nxt)==0){ q.push({nxt, {cnt+1, i}}); }
        }
    }
}
void solve()
{
    cin >> n;
    string s;
    vector< pair<int, int> > v;
    for(int i=0; i<n; i++){
        int a; cin >> a;
        v.push_back({a, i});
        s+=(i+'1');
    }
    sort(v.begin(), v.end());
    string ans;
    for(int i=n-1; i>=0; i--){
        ans+=v[i].second+'1';
    }
    cout << BFS(s, ans) << "\n";
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){ solve(); }
    return 0;
}

Compilation message

pancake.cpp: In function 'int BFS(std::string, std::string)':
pancake.cpp:13:44: warning: control reaches end of non-void function [-Wreturn-type]
   13 |     queue< pair<string, pair<int, int> > > q;
      |                                            ^

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 2668 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1085 ms 2668 KB Time limit exceeded