QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#548423 | #6353. Kth Lex Min Min Min Subpalindromes | MoyunAllgorithm# | RE | 0ms | 0kb | C++14 | 3.0kb | 2024-09-05 18:11:29 | 2024-09-05 18:11:30 |
answer
#include <bits/stdc++.h>
#define LL long long
#define int long long
using namespace std;
const int MAXN=1e6+5;
int N,M;
LL K;
void Func1()
{
if(K!=1)
{
puts("-1");
exit(0);
}
for(int i=1;i<=N;i++) printf("1 ");
exit(0);
}
int tab[13]={0,112122,112212,121122,121221,122112,122121,211212,211221,212112,212211,221121,221211};
void Func2()
{
int kkk=2*N-2;
if(K>kkk)
{
puts("-1");
exit(0);
}
if(N==1)
{
printf("%d\n",K);
exit(0);
}
if(N==2)
{
if(K==1) puts("1 2");
if(K==2) puts("2 1");
exit(0);
}
if(N==3)
{
if(K==1) puts("1 1 2");
if(K==2) puts("1 2 1");
if(K==3) puts("1 2 2");
if(K==4) puts("2 1 1");
if(K==5) puts("2 1 2");
if(K==6) puts("2 2 1");
exit(0);
}
if(N==4)
{
if(K==1) puts("1 1 2 1");
if(K==2) puts("1 1 2 2");
if(K==3) puts("1 2 1 1");
if(K==4) puts("1 2 1 2");
if(K==5) puts("1 2 2 1");
if(K==6) puts("2 1 1 2");
if(K==7) puts("2 1 2 1");
if(K==8) puts("2 1 2 2");
if(K==9) puts("2 2 1 1");
if(K==10) puts("2 2 1 2");
exit(0);
}
if(N==5)
{
if(K==1) puts("1 1 2 1 2");
if(K==2) puts("1 1 2 2 1");
if(K==3) puts("1 2 1 1 2");
if(K==4) puts("1 2 1 2 2");
if(K==5) puts("1 2 2 1 1");
if(K==6) puts("1 2 2 1 2");
if(K==7) puts("2 1 1 2 1");
if(K==8) puts("2 1 1 2 2");
if(K==9) puts("2 1 2 1 1");
if(K==10) puts("2 1 2 2 1");
if(K==11) puts("2 2 1 1 2");
if(K==12) puts("2 2 1 2 1");
exit(0);
}
int term=N/6;
N-=term*6;
int c[10];
for(int i=6;i;i--)
{
c[i]=tab[K]%10;
tab[K]/=10;
}
for(int i=1;i<=term;i++)
{
printf("%lld %lld %lld %lld %lld %lld ",c[1],c[2],c[3],c[4],c[5],c[6]);
}
for(int i=1;i<=N;i++) printf("%lld ",c[i]);
puts("");
exit(0);
}
LL cnt[MAXN];
int a[MAXN];
signed main()
{
//freopen("moyun.in","r",stdin);
freopen("moyun.out","w",stdout);
scanf("%lld %lld %lld",&N,&M,&K);
if(M<3)
{
for(int i=1;i;i=i) N++;
return 0;
}
if(M==1) Func1();
if(M==2) Func2();
if(N==1)
{
if(K>M) puts("-1");
else printf("%lld\n",K);
return 0;
}
a[0]=3;
for(int i=1;i<=N;i++)
{
if(a[i-1]==3) a[i]=1;
else a[i]=a[i-1]+1;
}
cnt[N]=M-2;
if(N==2) cnt[N]++;
int S=0;
for(int i=N-1;i;i--)
{
int nxt=M-2+(i<=2)+(i<=1);
__int128 ncnt=(__int128)cnt[i+1]*nxt;
if(ncnt>(__int128)K)
{
S=i;
LL t=(K+cnt[i+1]-1)/cnt[i+1];
K-=cnt[i+1]*(t-1);
if(i>2)
{
t+=1ll*min(a[i-1],a[i-2])<=t;
t+=1ll*max(a[i-1],a[i-2])<=t;
}
if(i==2) t+=1ll*a[i-1]<=t;
a[i]=t;
break;
}
cnt[i]=cnt[i+1]*nxt;
}
// printf("%lld\n",K);
if(S==0&&cnt[1]<K)
{
puts("-1");
return 0;
}
for(int i=S+1;i<N;i++)
{
LL t=(K+cnt[i+1]-1)/cnt[i+1];
K-=cnt[i+1]*(t-1);
if(i>2)
{
t+=1ll*min(a[i-1],a[i-2])<=t;
t+=1ll*max(a[i-1],a[i-2])<=t;
}
if(i==2) t+=1ll*a[i-1]<=t;
a[i]=t;
}
if(N>2)
{
K+=1ll*min(a[N-1],a[N-2])<=K;
K+=1ll*max(a[N-1],a[N-2])<=K;
}
if(N==2) K+=1ll*a[N-1]<=K;
a[N]=K;
for(int i=1;i<=N;i++) printf("%lld ",a[i]);
puts("");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Dangerous Syscalls
input:
1 1 1