Submission #367697

#	Time	Username	Problem	Language	Result	Execution time	Memory
367697		david0506	Pancake (NOI12_pancake)	C++14	20 / 25	1085 ms	2668 KiB

pancake

#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 (stderr)

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 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 8 / 8
• Subtask 5: 0 / 5