Submission #914838

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
914838	2024-01-22T18:10:27 Z	starchan	Permutation (APIO22_perm)	C++17	Compilation error	0 ms	0 KB

perm

#include<bits/stdc++.h>
//#include "perm.h"
using namespace std;
#define int long long
#define double long double
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define MX (int)3e5+5
#define SSX (int)6
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
bool no_pre = true;
vector<pair<double, pair<in, vector<int>>>> bruter;
vector<pair<double, pair<in, vector<int>>>> brute;
bool valid(const vector<int> &t)
{
	vector<int> a(SSX+1, 0), b(SSX+1, 0);
	for(int i = 0; i < t.size(); i++)
	{
		if(t[i] > 0)
			a[t[i]]++;
		else
			b[-t[i]]++;
	}
	for(int i = 1; i <= SSX; i++)
	{
		if((a[i] >= 2) || (b[i] >= 2))
			return false;
		if(i && (a[i] < a[i+1]))
			return false;
		if(i && (b[i] < b[i+1]))
			return false;
	}
	return true;
}
int inc_sub(const vector<int> &t)
{
	if(t.empty())
		return 1;
	int n = t.size();
	int dp[n];
	int ans = 2;
	dp[0] = 1;
	for(int i = 1; i < n; i++)
	{
		dp[i] = 1;
		for(int j = 1; j < i; j++)
		{
			if(t[j] < t[i])
				dp[i]+=dp[j];
		}
		ans+=dp[i];
	}
	return ans;
}
in linear(const vector<int> &v)
{
	vector<int> b;
	for(int k: v)
	{
		if(k > 0)
			b.pb(k);
	}
	int X = inc_sub(b);
	int Y = inc_sub(v);
	return {X, Y-X};
}
void assimilate(int u)
{
	vector<int> v;
	int k = 1;
	for(int i = 1; i <= u; i++)
	{
		k*=(2*i);
		v.pb(-i);
		v.pb(i);
	}
	vector<int> ch;
	for(int msk = 0; msk < k; msk++)
	{
		ch.clear();
		int cop = msk;
		for(int i = 1; i <= u; i++)
		{
			ch.pb(v[cop%(2*u)]);
			cop/=(2*u);
		}
		if(valid(ch))
		{
			auto ab = linear(ch);
			double U = u;
			double a = ab.f;
			double b = log(a);
			U = U/b;
			bruter.pb({U, {ab, ch}});
		}
	}
}
void pre()
{
	assert(no_pre);
	no_pre = false;
	for(int i = 1; i <= SSX; i++)
		assimilate(i);
	sort(bruter.begin(), bruter.end());
	brute.pb(bruter[0]);
	in prev = bruter[0].s.f;
	for(int k = 1; k < bruter.size(); k++)
	{
		if(bruter[k].s.f == prev)
			continue;
		brute.pb(bruter[k]);
		prev = bruter[k].s.f;
	}
	return;
}
void bruh(vector<int> &x, int v)
{
	if(v == 1)
		return;
	for(int i = 0; i < brute.size(); i++)
	{
		auto [a, b] = brute[i].s.f;
		if(v <= b)
			continue;
		if(v > b)
		{
			if((v-b)%a)
				continue;
			v-=b;
			v/=a;
			bruh(x, v);
			x.pb(i);
			return;
		}
	}
	return;
}
vector<signed> construct_permutation(int K)
{
	if(no_pre)
		pre();
	vector<int> d;
	bruh(d, K);
	int lb = 1;
	int ub = 0;
	vector<signed> v;
	for(int i = 0; i < d.size(); i++)
	{
		int t1 = 0;
		int t2 = 0;
		for(int k: brute[d[i]].s.s)
		{
			if(k > 0)
			{
				t1 = max(t1, k);
				v.pb((signed)(ub+k));
			}
			else
			{
				t2 = min(t2, k);
				v.pb((signed)(lb+k));
			}
		}
		lb+=t2;
		ub+=t1;
	}
	signed KK = 200;
	for(auto r: v)
		KK = min(KK, r);
	for(int i = 0; i < v.size(); i++)
		v[i]-=(KK-1);
	return v;
}
signed main()
{
	int n;
	cin >> n;
	vector<signed> kk = construct_permutation(n);
	cout << "perm size =  " << kk.size() << endl;
	for(auto pp: kk)
		cout << pp << " ";
	return 0;
}

Compilation message

perm.cpp: In function 'bool valid(const std::vector<long long int>&)':
perm.cpp:21:19: 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]
   21 |  for(int i = 0; i < t.size(); i++)
      |                 ~~^~~~~~~~~~
perm.cpp: In function 'void pre()':
perm.cpp:111:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long double, std::pair<std::pair<long long int, long long int>, std::vector<long long int> > > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |  for(int k = 1; k < bruter.size(); k++)
      |                 ~~^~~~~~~~~~~~~~~
perm.cpp: In function 'void bruh(std::vector<long long int>&, long long int)':
perm.cpp:124:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long double, std::pair<std::pair<long long int, long long int>, std::vector<long long int> > > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |  for(int i = 0; i < brute.size(); i++)
      |                 ~~^~~~~~~~~~~~~~
perm.cpp: In function 'std::vector<int> construct_permutation(long long int)':
perm.cpp:151:19: 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]
  151 |  for(int i = 0; i < d.size(); i++)
      |                 ~~^~~~~~~~~~
perm.cpp:174:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |  for(int i = 0; i < v.size(); i++)
      |                 ~~^~~~~~~~~~
/usr/bin/ld: /tmp/ccP3mgyp.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccCeUNsl.o:perm.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status