oj.uz

답안 #914853

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
914853 2024-01-22T18:31:27 Z starchan 순열 (APIO22_perm) C++17
100 / 100
 199 ms 1356 KB 
#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 = 0; 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*u);
		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);
	return v;
}
/*signed main()
{
	srand(time(0));
	for(int i = 1e18; i <= 1e18+100; i++)
	{
	
	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++)
      |                 ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 173 ms 1028 KB Output is correct
2 Correct 173 ms 1228 KB Output is correct

Subtask #2
90.0 / 90.0

# 결과 실행 시간 메모리 Grader output
1 Correct 173 ms 1028 KB Output is correct
2 Correct 173 ms 1228 KB Output is correct
3 Correct 192 ms 1316 KB Output is correct
4 Correct 176 ms 1260 KB Output is correct
5 Correct 181 ms 1224 KB Output is correct
6 Correct 191 ms 1356 KB Output is correct
7 Correct 178 ms 1212 KB Output is correct
8 Correct 175 ms 1228 KB Output is correct
9 Correct 176 ms 1228 KB Output is correct
10 Correct 199 ms 1088 KB Output is correct
11 Correct 177 ms 1300 KB Output is correct
12 Correct 184 ms 1072 KB Output is correct
13 Correct 179 ms 1172 KB Output is correct