QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#101859 | #6353. Kth Lex Min Min Min Subpalindromes | zhouhuanyi# | WA | 79ms | 17268kb | C++11 | 2.0kb | 2023-05-01 14:41:43 | 2023-05-01 14:41:46 |
Judging History
answer
#include<iostream>
#include<cstdio>
#define N 1000000
#define inf 1e9
using namespace std;
long long read()
{
char c=0;
long long sum=0;
while (c<'0'||c>'9') c=getchar();
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
int n,m,a[N+1],b[N+1];
long long k,pw[N+1];
bool check(int l,int r)
{
bool op=1;
for (int i=l;i<=r;++i) op&=(a[i]==a[l+r-i]);
return op;
}
void dfs(int x,int cnt)
{
if (x==n+1)
{
if ((x==1||cnt==((n-1)<<1))&&k)
{
k--;
if (!k)
{
for (int i=1;i<=n;++i) b[i]=a[i];
}
}
return;
}
int rst=0;
a[x]=1;
for (int i=max(x-6,1);i<=x;++i)
if (check(i,x))
rst++;
if (x<=2||cnt+rst<=((x-1)<<1)) dfs(x+1,cnt+rst);
a[x]=2,rst=0;
for (int i=max(x-6,1);i<=x;++i)
if (check(i,x))
rst++;
if (x<=2||cnt+rst<=((x-1)<<1)) dfs(x+1,cnt+rst);
return;
}
int main()
{
int x,y;
long long d,cnt;
n=read(),m=read(),k=read();
if (m==1)
{
if (k>1) puts("-1");
else
{
for (int i=1;i<=n;++i) printf("1 ");
puts("");
}
}
else if (m==2)
{
dfs(1,0);
if (k) puts("-1");
else
{
for (int i=1;i<=n;++i) printf("%d ",b[i]);
puts("");
}
}
else if (n==1)
{
if (k>m) puts("-1");
else
{
for (int i=1;i<=n;++i) printf("%lld ",k);
puts("");
}
}
else
{
pw[0]=1;
for (int i=1;i<=n;++i) pw[i]=min((__int128)(pw[i-1])*(m-2),(__int128)(k+1));
if (k>min((__int128)(pw[n-2])*(m-1)*m,(__int128)(k+1))) puts("-1");
else
{
k--;
for (int i=1;i<=n;++i)
{
if (i==1) d=min((__int128)(pw[n-2])*(m-1),(__int128)(k+1));
else d=pw[n-i];
cnt=k/d+1,k%=d,x=y=inf;
if (i-2>=1) x=a[i-2];
if (i-1>=1) y=a[i-1];
if (x>y) swap(x,y);
if (cnt>=x) cnt++;
if (cnt>=y) cnt++;
a[i]=cnt;
}
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: 2ms
memory: 5452kb
input:
1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 1ms
memory: 7568kb
input:
2 2 2
output:
2 1
result:
ok 2 number(s): "2 1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 7460kb
input:
3 3 3
output:
2 1 3
result:
ok 3 number(s): "2 1 3"
Test #4:
score: 0
Accepted
time: 1ms
memory: 7572kb
input:
9 9 8244353
output:
2 4 1 2 6 8 1 2 7
result:
ok 9 numbers
Test #5:
score: 0
Accepted
time: 2ms
memory: 5396kb
input:
10 7 998244353
output:
-1
result:
ok 1 number(s): "-1"
Test #6:
score: 0
Accepted
time: 3ms
memory: 7588kb
input:
3 1000 994253860
output:
998 244 353
result:
ok 3 number(s): "998 244 353"
Test #7:
score: 0
Accepted
time: 3ms
memory: 7572kb
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: 2ms
memory: 5216kb
input:
58 4 864691128455135233
output:
-1
result:
ok 1 number(s): "-1"
Test #9:
score: 0
Accepted
time: 79ms
memory: 17056kb
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: 74ms
memory: 17268kb
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: 5396kb
input:
1 1 2
output:
-1
result:
ok 1 number(s): "-1"
Test #12:
score: -100
Wrong Answer
time: 1ms
memory: 7324kb
input:
1 2 2
output:
-1
result:
wrong answer 1st numbers differ - expected: '2', found: '-1'