oj.uz

Submission #197519

# Submission time Handle Problem Language Result Execution time Memory
197519 2020-01-21T13:30:04 Z handlename Pancake (NOI12_pancake) C++17
25 / 25
 335 ms 6960 KB 
#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

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.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
8.0 / 8.0

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

Subtask #5
5.0 / 5.0

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