Submission #582679

#	Time	Username	Problem	Language	Result	Execution time	Memory
582679		Theo830	Permutation (APIO22_perm)	C++17	100 / 100	2 ms	340 KiB

perm

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll INF = 1e9+7;

const ll MOD = 998244353;

typedef pair<ll,ll> ii;

#define iii pair<ii,ll>

#define ull unsigned ll

#define f(i,a,b) for(ll i = a;i < b;i++)

#define pb push_back

#define vll vector<ll>

#define F first

#define S second

#define all(x) (x).begin(), (x).end()

///I hope I will get uprating and don't make mistakes

///I will never stop programming

///sqrt(-1) Love C++

///Please don't hack me

///@TheofanisOrfanou Theo830

///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)

///Stay Calm

///Look for special cases

///Beware of overflow and array bounds

///Think the problem backwards

///Training

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

uniform_int_distribution<ll> distr;

ll rnd(ll a, ll b){return distr(rng)%(b-a+1)+a;}

#include "perm.h"

std::vector<int> construct_permutation(long long k){

    vector<int>ans;

    vector<int>vale;

    ll e = 0;

    while(k != 1){

        if((k % 3) == 0){

            k /= 3;

            vale.pb(1);

            e++;

        }

        else if((k % 2) == 0){

            k /= 2;

            vale.pb(2);

        }

        else if((k % 5) == 0){

            k /= 5;

            vale.pb(3);

            e += 2;

        }

        else if((k % 7) == 0){

            k /= 7;

            vale.pb(4);

            e += 3;

        }

        else{

            vale.pb(0);

            k--;

        }

    }

    ll n = vale.size() + e;

    ll l = 0,r = n-1;

    for(auto x:vale){

        if(x == 0){

            ans.pb(l);

            l++;

        }

        else if(x == 2){

            ans.pb(r);

            r--;

        }

        else if(x == 1){

            ans.pb(r - 1);

            ans.pb(r);

            r -= 2;

        }

        else if(x == 3){

            ans.pb(r - 1);

            ans.pb(r - 2);

            ans.pb(r);

            r -= 3;

        }

        else if(x == 4){

            ans.pb(r - 3);

            ans.pb(r - 1);

            ans.pb(r);

            ans.pb(r - 2);

            r -= 4;

        }

    }

    reverse(all(ans));

    return ans;

}

/*

static long long MX=1e18;



static bool check_permutation(vector<int> v)

{

	sort(v.begin(),v.end());

	for(int i=0;i<v.size();i++)

		if(v[i]!=i) return 0;

	return 1;

}



long long count_increasing(const vector<int>& v) {

  vector<long long> dp(v.size() + 1, 0);

  dp[0] = 1;

  for (int x : v)

  {

  	for (int i = 0; i <= x; i++)

  	{

  		dp[x+1] += dp[i];

  		dp[x+1] = min(dp[x+1],MX+1);

  	}

  }

  long long result = 0;

  for (int i = 0; i <= (int)v.size(); i++){

  	result += dp[i];

  	result = min(result,MX+1);

  }

  return result;

}



int main() {

	int t;

	while(1)

	{

		long long k;

		k = rnd(2,MX);

		vector<int> ret=construct_permutation(k);

		if(!check_permutation(ret))

		{

			printf("WA: Returned array is not a permutation\n");

			exit(0);

		}

		long long inc=count_increasing(ret);

		if(inc!=k)

		{

			if(inc==MX+1)

				printf("WA: Expected %lld increasing subsequences, found more than %lld\n",k, MX);

			else

				printf("WA: Expected %lld increasing subsequences, found %lld\n",k,inc);

			exit(0);

		}

		if((int)ret.size() > 97){

            cout<<ret.size()<<" "<<k<<endl;

            return 0;

		}

	}

	return 0;

}

*/

• Subtask 1: 10 / 10
• Subtask 2: 90 / 90