Submission #1229479

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229479		papaulo	Pancake (NOI12_pancake)	C++20	25 / 25	166 ms	66988 KiB

pancake

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
typedef pair<int, pii> piii;

#define BLOCK_SIZE 3
#define MAX_BLOCKS (1<<BLOCK_SIZE)
#define BLOCK_MASK (MAX_BLOCKS-1)
#define MAXV (1<<(BLOCK_SIZE*MAX_BLOCKS))
#define MAXV2 (MAXV/MAX_BLOCKS)
int rev[MAXV];
int rev2[MAXV2][8];
int breadth[MAXV];
queue<int> bfs;

#define RNG(i, a, b) for(int i=a;i<b;i++)

int reverse(int v, int i) {
    int ans=v&((1<<(BLOCK_SIZE*i))-1); 
    RNG(j, i, MAX_BLOCKS) {
        ans|=((v>>(j*BLOCK_SIZE))&BLOCK_MASK)<<((MAX_BLOCKS-1-j+i)*BLOCK_SIZE);
    }
    return ans;
}

void show(int v) {
    RNG(i, 0, MAX_BLOCKS) {
        cout << ((v>>(i*BLOCK_SIZE))&BLOCK_MASK) << " ";
    }
    cout << "\n";
}

void genbase() {
    queue<piii> q;
    RNG(i, 0, MAXV) breadth[i]=-1;
    q.push({0, {0, BLOCK_MASK}});
    while(!q.empty()) {
        piii pr=q.front();
        q.pop();
        int v=pr.first;
        pii p=pr.second;
        int i=p.first, mx=p.second;
        if(i==MAX_BLOCKS) {
            if(mx) continue;
            breadth[v]=0;
            bfs.push(v);
            continue;
        }
        int mnv=0;
        if(mx>1&&i>0) mnv=mx-1;
        RNG(j, mnv, mx+1) {
            q.push({v|(j*(1<<(i*BLOCK_SIZE))), {i+1, j}});
        }
    }
}

void dobfs() {
    while(!bfs.empty()) {
        int v=bfs.front();
        bfs.pop();
        RNG(j, 0, MAX_BLOCKS) {
            int re=reverse(v, j);
            if(breadth[re]<0) {
                breadth[re]=breadth[v]+1;
                bfs.push(re);
            }
        }
    }
}

void testcase() {
    int n;
    cin >> n;
    map<int, int> mp;
    set<int> st;
    vector<int> arr(n);
    RNG(i, 0, n) cin >> arr[i];
    while(n<8) {
        arr.insert(arr.begin(), 1e9);
        n++;
    }
    for(auto v : arr) st.insert(v);
    while(!st.empty()) {
        auto p = st.end();
        p--;
        int v=*p;
        st.erase(p);
        mp[v]=st.size();
    }
    int binv=0;
    reverse(arr.begin(), arr.end());
    for(auto v : arr) {
        binv*=MAX_BLOCKS;
        binv+=mp[v];
    }
    //show(binv);
    cout << breadth[binv] << "\n";
}

int main() {
    auto start = chrono::high_resolution_clock::now();
    genbase();
    dobfs();
    auto end = chrono::high_resolution_clock::now();
    auto dur=chrono::duration<double>(end-start).count();
    int t;
    cin >> t;
    while(t--) {
        testcase();
    }
    return 0;
}

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