QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#101858 | #6353. Kth Lex Min Min Min Subpalindromes | zhouhuanyi# | WA | 3ms | 7604kb | C++11 | 1.9kb | 2023-05-01 14:39:37 | 2023-05-01 14:39:39 |
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 (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: 3ms
memory: 5360kb
input:
1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 7604kb
input:
2 2 2
output:
1 2
result:
wrong answer 1st numbers differ - expected: '2', found: '1'