Untitled

Run Settings
LanguageC++
Language Version
Run Command
#include<bits/stdc++.h> using namespace std; map<vector<int>,int> mp; int rep(vector<int> &a){ if(a.empty()){return 0;} if(mp.find(a)!=mp.end()){ return mp[a]; } int res=0; for(int i=1;i<a.size();i++){ if(a[i-1]==i){ vector<int> und; for(int j=0;j<a.size();j++){ if(j==i-1 || j==i){continue;} und.push_back(a[j]); } res=max(res,rep(und)+1); } } mp[a]=res; return res; } int pow(int a,int b){int i,r=1;for(i=1;i<=b;i++){r*=a;}return r;} int greedy(vector<int> a){ int res=0; while(true){ bool fin=true; for(int i=((int)a.size())-1;i>=1;i--){ if(a[i-1]==i){ vector<int> na; for(int j=0;j<a.size();j++){ if(j==i-1 || j==i){continue;} na.push_back(a[j]); } res++; a=na; fin=false; break; } } if(fin){break;} } return res; } int main(){ std::random_device seed_gen; std::mt19937_64 engine(seed_gen()); int fail=0; while(true){ if(mp.size()>2e6){mp.clear();} int n=1+(engine()%30); vector<int> a(n); for(auto &nx : a){ nx=rand()%n+1; } int ok=rep(a); int gd=greedy(a); if(ok!=gd){ cout << a.size() << "\n"; for(auto &nx : a){ cout << nx << " "; }cout << "\n"; cout << ok << " " << gd << "\n"; fail++; if(fail>=5){break;} } } return 0; }
Editor Settings
Theme
Key bindings
Full width
Lines