oj.uz

답안 #425439

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
425439 2021-06-13T03:56:14 Z errorgorn 팬케이크 정렬 (NOI12_pancake) C++17
25 / 25
 42 ms 4264 KB 
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <map>
using namespace std;
typedef pair<int,int> ii;
const long long INF=1000000000000000000;

vector<long long> precomp[10]; ///we shall precomp weights for pancake [0-8]
///i think we need to sort this then we can bsta

vector<long long> temp; ///we shall store the temporary stuff here
inline void propogate(long long i){
    long long pref=(i>>36);
    long long val;
    i&=(1LL<<(36))-1;
    for (int x=8;x>=0;x--){
        pref|=(i>>(x<<2))<<((9-x)<<2);
        i&=(1LL<<(x<<2))-1;
        val=(pref<<(x<<2))|i;
        temp.push_back(val);
    }
}

vector<long long> __q[4];
inline bool prop(long long i,int j){
    long long pref=(i>>36);
    long long val;
    i&=(1LL<<(36))-1;
    for (int x=8;x>=0;x--){
        pref|=(i>>(x<<2))<<((9-x)<<2);
        i&=(1LL<<(x<<2))-1;
        val=(pref<<(x<<2))|i;
        if ((*lower_bound(precomp[6].begin(),precomp[6].end(),val))==val) return true;
        if (j<=3){
            __q[j].push_back(val);
        }
    }
    return false;
}
int main(){
    //freopen("input.txt","r",stdin);
    precomp[0]=vector<long long>()={4886718345,INF}; ///this is base case
    precomp[1]=vector<long long>()={69311227785,141788800905,215021348745,288316811145,361617188745,434917934985,508218708105,581519483145,654820258320,INF};
    vector<long long>::iterator pnt,pnt2;
    for (int x=1;x<6;x++){
        for (auto &it:precomp[x]) propogate(it);
        sort(temp.begin(),temp.end());
        precomp[x-1].push_back(INF);
        pnt=precomp[x-1].begin(),pnt2=precomp[x].begin();

        for (auto &it:temp){
            if (!precomp[x+1].empty() && precomp[x+1].back()==it) continue;
            while ((*pnt)<it) pnt++;
            while ((*pnt2)<it) pnt2++;
            if ((*pnt)!=it && (*pnt2)!=it) precomp[x+1].push_back(it);
        }
        temp.clear();
        precomp[x+1].push_back(INF);
    }

    int TC;
    scanf("%d",&TC);
    int n;
    int arr[10];
    vector<int> v;
    map<int,int> m;
    long long original;
    while(TC--){
        v.clear();
        m.clear();
        scanf("%d",&n);
        for (int x=0;x<n;x++) scanf("%d",&arr[x]),v.push_back(arr[x]);
        for (int x=n;x<10;x++) arr[x]=x;

        sort(v.begin(),v.end());
        reverse(&arr[0],&arr[n]);
        for (int x=0;x<n;x++) m[v[x]]=x;
        for (int x=0;x<n;x++) arr[x]=m[arr[x]];

        original=arr[0];
        for (int x=1;x<10;x++){
            original=(original<<4)|arr[x];
        }

        for (int x=0;x<7;x++){
            if ((*lower_bound(precomp[x].begin(),precomp[x].end(),original))==original){
                printf("%d\n",x);
                goto _end;
            }
        }

        for (int x=0;x<=3;x++) __q[x].clear();
        __q[0].push_back(original);

        for (int x=0;x<=3;x++){
            for (auto &it:__q[x]){
                if (prop(it,x+1)){
                    printf("%d\n",x+7);
                    goto _end;
                }
            }
        }

        printf("11\n");
        _end:;
    }
}

Compilation message

pancake.cpp: In function 'int main()':
pancake.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |     scanf("%d",&TC);
      |     ~~~~~^~~~~~~~~~
pancake.cpp:73:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |         scanf("%d",&n);
      |         ~~~~~^~~~~~~~~
pancake.cpp:74:36: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         for (int x=0;x<n;x++) scanf("%d",&arr[x]),v.push_back(arr[x]);
      |                               ~~~~~^~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 4244 KB Output is correct

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 4256 KB Output is correct

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 4244 KB Output is correct

Subtask #4
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 4244 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 4264 KB Output is correct