QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #548456 | #6353. Kth Lex Min Min Min Subpalindromes | MoyunAllgorithm# | WA | 42ms | 12760kb | C++14 | 3.1kb | 2024-09-05 18:39:52 | 2024-09-05 18:39:53 |
Judging History
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=12;
if(N==1) kkk=1;
if(N==2) kkk=2;
if(N==3) kkk=6;
if(N==4) kkk=10;
if(K>kkk)
{
puts("-1");
exit(0);
}
if(N==1)
{
if(K<=2) 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;
}
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: 100
Accepted
time: 0ms
memory: 3708kb
input:
1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
2 2 2
output:
2 1
result:
ok 2 number(s): "2 1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 5952kb
input:
3 3 3
output:
2 1 3
result:
ok 3 number(s): "2 1 3"
Test #4:
score: 0
Accepted
time: 0ms
memory: 6008kb
input:
9 9 8244353
output:
2 4 1 2 6 8 1 2 7
result:
ok 9 numbers
Test #5:
score: 0
Accepted
time: 0ms
memory: 5816kb
input:
10 7 998244353
output:
-1
result:
ok 1 number(s): "-1"
Test #6:
score: 0
Accepted
time: 0ms
memory: 5964kb
input:
3 1000 994253860
output:
998 244 353
result:
ok 3 number(s): "998 244 353"
Test #7:
score: 0
Accepted
time: 1ms
memory: 5964kb
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: 1ms
memory: 5776kb
input:
58 4 864691128455135233
output:
-1
result:
ok 1 number(s): "-1"
Test #9:
score: 0
Accepted
time: 42ms
memory: 12760kb
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: 39ms
memory: 11964kb
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: 0ms
memory: 3840kb
input:
1 1 2
output:
-1
result:
ok 1 number(s): "-1"
Test #12:
score: -100
Wrong Answer
time: 0ms
memory: 3736kb
input:
1 2 2
output:
-1
result:
wrong answer 1st numbers differ - expected: '2', found: '-1'