Source Code
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

const int N=2e5+1;

int spf[N];

void sieve() {
  for (int i = 2; i < N; i += 2)
    spf[i] = 2;
  
  for (int i = 3; i < N; i += 2)
    spf[i] = i;

  for (int i = 3; i * i < N; i += 2) {
    if (spf[i] == i) {
      for (int j = i * i; j < N; j += (i << 1))
        spf[j] = i;
    }
  }
}

bool isprime(int n) {
  return (n == spf[n]);
}

vector<pair<int, int>> factorize(int n) {
  vector<pair<int, int>> ret;
  while (n != 1) {
    int cnt = 0;
    int x = spf[n];
    while (n % x == 0) {
      ++cnt;
      n /= x;
    }
    ret.emplace_back(x, cnt);
  }
  return ret;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin>>n;

    vector<int>a(n);
    for(auto &x:a) cin>>x;

    // step 1
    a.push_back(0);

    // step 2
    for(int i=0;i<n;i++){
        a[i]=max(a[i],a[i+1]);
    }

    // step 3 and 4
    int org=n;
    n=a.size();

    function<void()>step34=[&](){
        n=a.size();
        if(n%2==0){
            reverse(a.begin(),a.begin()+n/2);
            reverse(a.begin()+n/2,a.end());
        } else {
            ll sum=0;
            while(!a.empty()){
                sum+=a.back();
                if(sum>org){
                    break;
                }
                a.pop_back();
            }
            step34();
        }
    };
    step34();

    sieve();
    function<void()>step5to13=[&](){
        // step 5
        a.push_back(3);
        a.push_back(2);
        a.push_back(1);
        n=a.size();

        // step 6
        for(int i=0;i<n;i++){
            if(a[i]>a[n-1]){
                swap(a[i],a[n-1]);
            }
        }

        // step 7
        a[0]=1031;

        // step 8
        for(int i=0;i<n;i++){
            if(a[i]<=1) continue;
            vector<pair<int,int>>fact=factorize(a[i]);
            sort(fact.begin(),fact.end());
            a[i]=fact.back().first;
        }

        // step 9
        sort(a.rbegin(),a.rend());

        // step 10
        for(int i=0;i<n;i++){
            a[i]%=16384;
        }

        // step 11
        for(int i=1;i+2<n;i++){
            if(a[i]==6&&a[i+1]==7&&a[i+2]==9){
                swap(a[i],a[i-1]);
            }
        }

        // step 12
        for(int i=0;i<n;i++){
            a[i]=a[i]*__builtin_popcount(a[i]);
        }

        // step 13
        if(a.size()%2){
            step5to13();
        }
    };
    step5to13();

    if(!a[0]||!a.back()){
        a={1,2,3,4,5};
    }

    n=a.size();

    ll ans=0;
    for(int i=0;i<n;i++){
        ans+=(i+1)*a[i];
    }

    cout<<ans;
}
Copy
Slavery YazanIstatiyeh
GNU G++17
25 ms
2.2 MB
Runtime Error