oj.uz

Submission #1095517

# Submission time Handle Problem Language Result Execution time Memory
1095517 2024-10-02T13:07:15 Z SoMotThanhXuan Pancake (NOI12_pancake) C++17
25 / 25
 54 ms 2400 KB 
#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

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

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

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
8.0 / 8.0

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

Subtask #5
5.0 / 5.0

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