QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #507283 | #6353. Kth Lex Min Min Min Subpalindromes | ucup-team052# | AC ✓ | 983ms | 255508kb | C++23 | 4.2kb | 2024-08-06 15:16:21 | 2024-08-06 15:16:22 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
using LL=long long;
const __int128 INF=1000000000000000005;
const LL inf=1000000000000000005;
#define N 1000005
#define int long long
int mul(int x,int y){return min((__int128)x*y,INF);}
int add(int x,int y){return min(x+y,inf);}
int a[N],pw[N],n,m,k;
const int L=5,ful=(1<<L)-1;
int f[N][1<<5],v[20],ok[1<<5],ok2[1<<5][2];
signed main(){
#ifdef xay5421
// cout<<sizeof(f)/1024.0/1024<<endl;
int n=9,mn=inf,ccnt=0;
for(int st=0;st<1<<n;st++)
{
for(int i=0;i<n;i++) v[i]=st>>i&1;
int cnt=0;
for(int i=0;i<n;i++) for(int j=i;j<n;j++)
{
int len=j-i+1;
int ok=1;
for(int l=0;l<len;l++) ok&=v[i+l]==v[j-l];
cnt+=ok;
}
if(cnt==2*n-2)
{
// for(int i=0;i<n;i++) printf("%d%c",v[n-i-1]+1," \n"[i==n-1]);
}
}
// cout<<mn<<" "<<ccnt<<endl;
freopen("b.in","r",stdin);
#endif
cin>>n>>m>>k;
if(m==1)
{
if(k>1) printf("-1\n");
else
{
for(int i=1;i<=n;i++) printf("1%c"," \n"[i==n]);
}
}
else if(n==1)
{
if(k>m) printf("-1\n");
else printf("%lld\n",k);
}
else if(m==2)
{
/*
for(int st=0;st<1<<L;st++)
{
ok[st]=1;
for(int j=0;j+2<L;j++) if((st>>j&7)==0||(st>>j&7)==7) ok[st]=0;
for(int j=0;j<L;j++) v[j]=st>>j&1;
for(int j=0;j<L;j++) ok[st]&=v[j]==v[L-j-1];
}
for(int st=0;st<1<<L;st++) for(int c=0;c<2;c++)
{
ok2[st][c]=1;
int tst=st<<1|c;
for(int j=0;j+2<=L;j++) if((tst>>j&7)==0||(tst>>j&7)==7) ok2[st][c]=0;
for(int j=0;j<=L;j++) v[j]=tst>>j&1;
for(int j=0;j<=L;j++) ok2[st][c]&=v[j]==v[L-j-1];
}
*/
f[n+1][0]=1;
for(int i=n;i>=1;i--) for(int st=0;st<1<<L;st++) if(f[i+1][st])
{
for(int j=0;j<L;j++) v[j+1]=st>>j&1;
for(int c=0;c<2;c++)
{
v[0]=c;
if(i+2<=n)
{
if(v[0]==v[1]&&v[1]==v[2]) continue;
}
if(i+4<=n)
{
int ok=1;
for(int j=0;j<L;j++) ok&=v[j]==v[L-j-1];
if(ok) continue;
}
if(i+5<=n)
{
int ok=1;
for(int j=0;j<=L;j++) ok&=v[j]==v[L-j];
if(ok) continue;
}
int nst=(st<<1|c)&ful;
f[i][nst]=add(f[i][nst],f[i+1][st]);
}
}
int sum=0;
for(int j=0;j<1<<L;j++) sum=add(sum,f[1][j]);
// printf("%lld\n",sum);
if(sum<k) printf("-1\n");
else
{
if(n==2)
{
if(k==1) printf("1 2\n");
else if(k==2) printf("2 1\n");
else printf("-1\n");
return 0;
}
int lst=0;
for(int i=1;i<=n;i++)
{
for(int c=0;c<2;c++)
{
int all=0;
for(int st=0;st<1<<L;st++)
{
if((st&1)!=c) continue;
int cv=0;
for(int j=0;j<min(L,i-1);j++) v[cv++]=lst>>j&1;
reverse(v,v+cv);
for(int j=0;j<L&&i+j<=n;j++) v[cv++]=st>>j&1;
int ok=1;
for(int i=0;i+2<cv;i++)
{
if(v[i]==v[i+1]&&v[i+1]==v[i+2]) ok=0;
}
for(int i=0;i+4<cv;i++)
{
if(v[i]==v[i+4]&&v[i+1]==v[i+3]) ok=0;
}
for(int i=0;i+5<cv;i++)
{
if(v[i]==v[i+5]&&v[i+1]==v[i+4]&&v[i+2]==v[i+3]) ok=0;
}
if(!ok) continue;
// printf("* %d %d %d\n",i,st,f[i][st]);
all=add(all,f[i][st]);
}
if(all<k) k-=all;
else
{
lst=(lst<<1|c)&ful;
printf("%lld%c",c+1," \n"[i==n]);
break;
}
}
}
}
}
else
{
pw[0]=1;
for(int i=1;i<=n;i++) pw[i]=mul(pw[i-1],m-2);
pw[n-1]=mul(pw[n-2],m-1);
pw[n]=mul(pw[n-1],m);
if(pw[n]<k) printf("-1\n");
else
{
int l0=-1,l1=-1;
for(int i=n;i>=1;i--)
{
for(int j=1;j<=m;j++)
{
if(j==l0||j==l1) continue;
if(k>pw[i-1]) k-=pw[i-1];
else
{
printf("%lld%c",j," \n"[i==1]);
l1=l0,l0=j;
break;
}
}
}
}
}
return 0;
}
/*
* 1 0
* 1 2
* 1 4
* 1 6
* 1 8
* 1 10
* 1 12
* 1 14
* 1 16
* 1 18
* 1 20
* 1 22
* 1 24
* 1 26
* 1 28
* 1 30
1 * 2 0
* 2 2
* 2 4
* 2 6
* 2 8
* 2 10
* 2 12
* 2 14
* 2 16
* 2 18
* 2 20
* 2 22
* 2 24
* 2 26
* 2 28
* 2 30
* 2 1
* 2 3
* 2 5
* 2 7
* 2 9
* 2 11
* 2 13
* 2 15
* 2 17
* 2 19
* 2 21
* 2 23
* 2 25
* 2 27
* 2 29
* 2 31
2
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5672kb
input:
1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5708kb
input:
2 2 2
output:
2 1
result:
ok 2 number(s): "2 1"
Test #3:
score: 0
Accepted
time: 1ms
memory: 5800kb
input:
3 3 3
output:
2 1 3
result:
ok 3 number(s): "2 1 3"
Test #4:
score: 0
Accepted
time: 1ms
memory: 5844kb
input:
9 9 8244353
output:
2 4 1 2 6 8 1 2 7
result:
ok 9 numbers
Test #5:
score: 0
Accepted
time: 1ms
memory: 5868kb
input:
10 7 998244353
output:
-1
result:
ok 1 number(s): "-1"
Test #6:
score: 0
Accepted
time: 1ms
memory: 5796kb
input:
3 1000 994253860
output:
998 244 353
result:
ok 3 number(s): "998 244 353"
Test #7:
score: 0
Accepted
time: 1ms
memory: 5788kb
input:
58 4 864691128455135232
output:
4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4
result:
ok 58 numbers
Test #8:
score: 0
Accepted
time: 0ms
memory: 5776kb
input:
58 4 864691128455135233
output:
-1
result:
ok 1 number(s): "-1"
Test #9:
score: 0
Accepted
time: 43ms
memory: 13972kb
input:
1000000 1000000 1000000000000000000
output:
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 ...
result:
ok 1000000 numbers
Test #10:
score: 0
Accepted
time: 47ms
memory: 14048kb
input:
1000000 4 1000000000000000000
output:
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 ...
result:
ok 1000000 numbers
Test #11:
score: 0
Accepted
time: 1ms
memory: 5704kb
input:
1 1 2
output:
-1
result:
ok 1 number(s): "-1"
Test #12:
score: 0
Accepted
time: 1ms
memory: 5840kb
input:
1 2 2
output:
2
result:
ok 1 number(s): "2"
Test #13:
score: 0
Accepted
time: 1ms
memory: 5668kb
input:
2 2 1
output:
1 2
result:
ok 2 number(s): "1 2"
Test #14:
score: 0
Accepted
time: 1ms
memory: 5840kb
input:
3 2 4
output:
2 1 1
result:
ok 3 number(s): "2 1 1"
Test #15:
score: 0
Accepted
time: 1ms
memory: 5724kb
input:
3 2 7
output:
-1
result:
ok 1 number(s): "-1"
Test #16:
score: 0
Accepted
time: 1ms
memory: 5776kb
input:
4 2 10
output:
2 2 1 2
result:
ok 4 number(s): "2 2 1 2"
Test #17:
score: 0
Accepted
time: 1ms
memory: 5992kb
input:
4 2 3
output:
1 2 1 1
result:
ok 4 number(s): "1 2 1 1"
Test #18:
score: 0
Accepted
time: 1ms
memory: 5844kb
input:
5 2 7
output:
2 1 1 2 1
result:
ok 5 number(s): "2 1 1 2 1"
Test #19:
score: 0
Accepted
time: 0ms
memory: 5668kb
input:
5 2 13
output:
-1
result:
ok 1 number(s): "-1"
Test #20:
score: 0
Accepted
time: 1ms
memory: 5848kb
input:
6 2 5
output:
1 2 2 1 1 2
result:
ok 6 numbers
Test #21:
score: 0
Accepted
time: 947ms
memory: 254900kb
input:
1000000 2 3
output:
1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 ...
result:
ok 1000000 numbers
Test #22:
score: 0
Accepted
time: 983ms
memory: 255508kb
input:
1000000 2 5
output:
1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 ...
result:
ok 1000000 numbers
Test #23:
score: 0
Accepted
time: 961ms
memory: 255288kb
input:
1000000 2 7
output:
2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 ...
result:
ok 1000000 numbers
Test #24:
score: 0
Accepted
time: 216ms
memory: 255184kb
input:
1000000 2 1000000000000000000
output:
-1
result:
ok 1 number(s): "-1"
Test #25:
score: 0
Accepted
time: 1ms
memory: 5792kb
input:
1 3 2
output:
2
result:
ok 1 number(s): "2"
Test #26:
score: 0
Accepted
time: 1ms
memory: 5856kb
input:
2 3 5
output:
3 1
result:
ok 2 number(s): "3 1"
Test #27:
score: 0
Accepted
time: 46ms
memory: 14120kb
input:
1000000 3 5
output:
3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 ...
result:
ok 1000000 numbers
Test #28:
score: 0
Accepted
time: 4ms
memory: 11876kb
input:
1000000 3 7
output:
-1
result:
ok 1 number(s): "-1"
Test #29:
score: 0
Accepted
time: 48ms
memory: 14060kb
input:
1000000 4 211106232532991
output:
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 ...
result:
ok 1000000 numbers
Test #30:
score: 0
Accepted
time: 47ms
memory: 11988kb
input:
1000000 5 1000000000000000000
output:
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 ...
result:
ok 1000000 numbers
Test #31:
score: 0
Accepted
time: 51ms
memory: 13976kb
input:
1000000 123123 1000000000000000000
output:
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 ...
result:
ok 1000000 numbers
Test #32:
score: 0
Accepted
time: 1ms
memory: 5800kb
input:
6 1000000 1000000000000000000
output:
1 2 4 9 15 8
result:
ok 6 numbers
Test #33:
score: 0
Accepted
time: 1ms
memory: 5780kb
input:
4 1000000 1000000000000000000
output:
2 7 15 9
result:
ok 4 number(s): "2 7 15 9"
Test #34:
score: 0
Accepted
time: 2ms
memory: 5924kb
input:
3 1000000 999997000002000000
output:
1000000 999999 999998
result:
ok 3 number(s): "1000000 999999 999998"
Test #35:
score: 0
Accepted
time: 0ms
memory: 5716kb
input:
3 1000000 999997000002000001
output:
-1
result:
ok 1 number(s): "-1"