QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #548341 | #6353. Kth Lex Min Min Min Subpalindromes | MoyunAllgorithm# | WA | 41ms | 9360kb | C++14 | 3.1kb | 2024-09-05 17:20:01 | 2024-09-05 17:20:02 |
Judging History
answer
#include <bits/stdc++.h>
#define LL 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("%d %d %d %d %d %d ",c[1],c[2],c[3],c[4],c[5],c[6]);
}
for(int i=1;i<=N;i++) printf("%d ",c[i]);
puts("");
exit(0);
}
LL cnt[MAXN];
int a[MAXN];
int main()
{
scanf("%d %d %lld",&N,&M,&K);
// for(int i=1;i<=1;i=i) N++;
// return 0;
/*if(N>6&&M==2)
{
for(int i=1;i<=1;i=i) N++;
return 0;
}*/
if(M==1) Func1();
if(M==2) Func2();
if(N==1)
{
if(K>M) puts("-1");
else printf("%d\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;
//pri
LL t=(K+cnt[i+1]-1)/cnt[i+1];
if((__int128)cnt[i+1]*(t-1)>K)
{
printf("%lld %lld\n",cnt[i+1]*(t-1),K);
for(int i=1;i;i=i) N++;
}
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("%d %lld\n",i,cnt[i]);
}
// 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("%d ",a[i]);
puts("");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3836kb
input:
1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
2 2 2
output:
2 1
result:
ok 2 number(s): "2 1"
Test #3:
score: 0
Accepted
time: 1ms
memory: 6000kb
input:
3 3 3
output:
2 1 3
result:
ok 3 number(s): "2 1 3"
Test #4:
score: 0
Accepted
time: 1ms
memory: 5996kb
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: 5680kb
input:
10 7 998244353
output:
-1
result:
ok 1 number(s): "-1"
Test #6:
score: 0
Accepted
time: 1ms
memory: 6000kb
input:
3 1000 994253860
output:
998 244 353
result:
ok 3 number(s): "998 244 353"
Test #7:
score: 0
Accepted
time: 0ms
memory: 5792kb
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: 5824kb
input:
58 4 864691128455135233
output:
-1
result:
ok 1 number(s): "-1"
Test #9:
score: 0
Accepted
time: 41ms
memory: 9032kb
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: 41ms
memory: 9360kb
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: 3756kb
input:
1 1 2
output:
-1
result:
ok 1 number(s): "-1"
Test #12:
score: -100
Wrong Answer
time: 0ms
memory: 3820kb
input:
1 2 2
output:
-1
result:
wrong answer 1st numbers differ - expected: '2', found: '-1'