Submission #197519

#	Time	Username	Problem	Language	Result	Execution time	Memory
197519		handlename	Pancake (NOI12_pancake)	C++17	25 / 25	335 ms	6960 KiB

pancake

#include <bits/stdc++.h>
using namespace std;
vector<int> discretize(vector<int> v){
    vector<int> dis=v;
    sort(dis.begin(),dis.end());
    dis.resize(unique(dis.begin(),dis.end()) - dis.begin());
    for (int i=0;i<v.size();i++){
        v[i]=lower_bound(dis.begin(),dis.end(),v[i])-dis.begin();
    }
    return v;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin>>t;
    map<vector<int>,int> m;
    for (int i=1;i<=8;i++){
        vector<int> v;
        for (int j=i-1;j>=0;j--) v.push_back(j);
        queue<vector<int> > q;
        q.push(v);
        m[v]=0;
        while (!q.empty()){
            vector<int> cur=q.front();
            q.pop();
            for (int j=2;j<=i;j++){
                vector<int> temp=cur;
                auto it=temp.end()-j;
                reverse(it,temp.end());
                if (m.find(temp)==m.end() || m[temp]>m[cur]+1){
                    m[temp]=m[cur]+1;
                    q.push(temp);
                }
            }
        }
    }
    while (t--){
        int n;
        cin>>n;
        vector<int> v;
        for (int i=0;i<n;i++){
            int k;
            cin>>k;
            v.push_back(k);
        }
        v=discretize(v);
        cout<<m[v]<<'\n';
    }
}

Compilation message (stderr)

pancake.cpp: In function 'std::vector<int> discretize(std::vector<int>)':
pancake.cpp:7:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v.size();i++){
                  ~^~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 8 / 8
• Subtask 5: 5 / 5