Submission #1095517

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095517		SoMotThanhXuan	Pancake (NOI12_pancake)	C++17	25 / 25	54 ms	2400 KiB

pancake

#include <bits/stdc++.h>
using namespace std;
#define ii pair<int,int>
#define iii pair<int,ii>
#define vii vector<ii>
#define viii vector<iii>
#define priority_queue pq
int dx[]={1,-1,0,0,1,1,-1,-1};
int dy[]={0,0,1,-1,1,-1,-1,1};
void minimize(int &u,int v){
    if(v<u)u=v;
}
void maximize(int &u,int v){
    if(v>u)u=v;
}
void minimizell(long long &u,long long v){
    if(v<u)u=v;
}
void maximizell(long long &u,long long v){
    if(v>u)u=v;
}
const int N=1e5+2;
const int mod=1e9+7;
const int inf=1e9+8;
const long long infll=1e18+8;
int d[9],a[9];
map<int,int> f;
int changeState(int val,int i){
    int s=0;
    string t=" ";
    while(val){
        t.push_back(char(val%10+48));
        val/=10;
    }
    //cout << t << "\n";
    int res=0;
    for(int i=1;i<=4;++i){
        swap(t[i],t[8-i+1]);
    }
    for(int j=1;j<i;++j){
        res=res*10+t[j]-48;
    }
    for(int j=8;j>=i;--j){
        res=res*10+t[j]-48;
    }
    return res;
}
const int X=87654321;
void bfs(){
    f[87654321]=0;
    queue<int> q;
    q.push({87654321});
    while(!q.empty()){
        int val=q.front();
        int dis=f[val];
        q.pop();
        for(int i=1;i<=8;++i){
            int x=changeState(val,i);
            if(x!=X and f[x]==0){
                f[x]=dis+1;
                q.push(x);
            }
        }
    }
}
void init(){
    int t,n;
    cin >> t;
    bfs();
    while(t--){
        cin >> n;
        for(int i=1;i<=n;++i){
            cin >> a[i];
            d[i]=a[i];
        }
        sort(d+1,d+1+n);
        int res=0;
        for(int j=8;j>n;--j){
            res=res*10+j;
        }
        for(int i=1;i<=n;++i){
            a[i]=lower_bound(d+1,d+n+1,a[i])-d;
            res=res*10+a[i];
        }
        cout << f[res] << "\n";
    }
}
int main(){
    //freopen(".INP","r",stdin);
    //freopen(".OUT","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    init();
    return 0;
}

Compilation message (stderr)

pancake.cpp: In function 'int changeState(int, int)':
pancake.cpp:29:9: warning: unused variable 's' [-Wunused-variable]
   29 |     int s=0;
      |         ^

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