이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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*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()
{
srand(time(0));
vector<int> WW;
WW.pb(1);
WW.pb(2);
cout << inc_sub(WW) << "\n";
for(int i = 2; i <= 90; i++)
{
int MM = 9e16+(rand()%((int)(1e13)));
MM*=14;
MM++;
vector<signed> v = construct_permutation(MM);
printf("For %d used v.size() = %d", MM, (signed)v.size());
cout << endl;
vector<int> w;
for(auto kk: v)
{
cout << kk << " ";
w.pb(kk);
}
cout << endl;
assert((inc_sub(w) == MM));
}
return 0;
}*/
컴파일 시 표준 에러 (stderr) 메시지
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++)
| ~~^~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |