Submission #428624

#	Time	Username	Problem	Language	Result	Execution time	Memory
428624		kai824	Cheerleaders (info1cup20_cheerleaders)	C++17	26 / 100	2110 ms	381048 KiB

cheerleaders

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int b=2,b2=13,mod=1000000007;

int n;

int ft[150000];
#define ls(x) (x&(-x))
void update(int p){
  for(;p<=(1<<n);p+=ls(p))ft[p]++;
}
int query(int p){
  int ans=0;
  for(;p;p-=ls(p))ans+=ft[p];
  return ans;
}

int cnt(vector<int>&v){
  int ans=0;
  for(int i=1;i<=(1<<n);i++)ft[i]=0;
  for(int i=v.size()-1;i>=0;i--){
    ans+=query(v[i]+1);
    update(v[i]+1);
  }
  return ans;
}

typedef pair<int,int> pii;
map<pii,pair<pii,int> > dist;//last move...
int best;
pii hs;
pii hh(vector<int> &v){
  pii ans=make_pair(0,0);
  int a=1,a2=1;
  for(int i=0;i<v.size();i++){
    a*=b;a%=mod;
    a2*=b2;a2%=mod;
    ans.first+=(a*v[i])%mod;
    ans.second+=(a2*v[i])%mod;
  }
  ans.first%=mod;
  ans.second%=mod;
  return ans;
}
int kk;
pii pp;
void dfs(vector<int>&v,pii h){
  kk=cnt(v);
  if(kk<best){
    best=kk;
    hs=h;
  }
  vector<int> v2;

  if(dist[h].second!=1){
    //move 1:
    for(int i=(1<<(n-1));i<(1<<n);i++)v2.emplace_back(v[i]);
    for(int i=0;i<(1<<(n-1));i++)v2.emplace_back(v[i]);
    pp=hh(v2);
    if(dist.find(pp)==dist.end()){
      dist[pp]=make_pair(h,1);
      dfs(v2,pp);
    }
    v2.clear();
  }

  //move 2:
  for(int i=0;i<(1<<n);i+=2)v2.emplace_back(v[i]);
  for(int i=1;i<(1<<n);i+=2)v2.emplace_back(v[i]);
  pp=hh(v2);
  if(dist.find(pp)==dist.end()){
    dist[pp]=make_pair(h,2);
    dfs(v2,pp);
  }
}
void bt(pii x){
  if(dist[x].second==-1)return;
  bt(dist[x].first);
  cout<<dist[x].second;
}

int32_t main(){
  ios_base::sync_with_stdio(false);cin.tie(0);
  cin>>n;
  vector<int> v;
  for(int i=0;i<(1<<n);i++){
    int a;
    cin>>a;
    v.push_back(a);
  }
  if(n==0){
    cout<<"0\n2\n";
    return 0;
  }
  // if(n>11){main2();return 0;}
  best=1e18;hs=hh(v);
  dist[hs]=make_pair(hs,-1);
  dfs(v,hs);
  cout<<best<<'\n';
  bt(hs);
}

Compilation message (stderr)

cheerleaders.cpp: In function 'pii hh(std::vector<long long int>&)':
cheerleaders.cpp:36:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   for(int i=0;i<v.size();i++){
      |               ~^~~~~~~~~

• Subtask 1: 16 / 16
• Subtask 2: 10 / 10
• Subtask 3: 0 / 25
• Subtask 4: 0 / 21
• Subtask 5: 0 / 28