#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]);
| ~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
4244 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
4256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
4244 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
4244 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
4264 KB |
Output is correct |
