QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#149663 | #6353. Kth Lex Min Min Min Subpalindromes | qzez# | WA | 1ms | 5760kb | C++14 | 2.1kb | 2023-08-25 08:21:09 | 2023-08-25 08:21:12 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<typename T>
ostream& operator << (ostream &out,const vector<T>&x){
if(x.empty())return out<<"[]";
out<<'['<<x[0];
for(int len=x.size(),i=1;i<len;i++)out<<','<<x[i];
return out<<']';
}
template<typename T>
vector<T> ary(const T *a,int l,int r){
return vector<T>{a+l,a+1+r};
}
template<typename T>
void debug(T x){
cerr<<x<<'\n';
}
template<typename T,typename ...S>
void debug(T x,S ...y){
cerr<<x<<' ',debug(y...);
}
int calc(vector<int>a){
int n=a.size(),ans=0;
for(int i=0,j;i<n;i++){
for(j=0;i-j>=0&&i+j<n&&a[i-j]==a[i+j];j++);
ans+=j;
}
for(int i=0,j;i+1<n;i++){
for(j=0;i-j>=0&&i+j+1<n&&a[i-j]==a[i+1+j];j++);
ans+=j;
}
return ans;
}
vector<int> gen(int S,int n){
vector<int>a;
for(int i=n-1;i>=0;i--)a.push_back(S>>i&1);
return a;
}
const int N=1e6+10;
int n,m,k;
void solve(){
int n=min(::n,6),U=(1<<n)-1,mn=n*n;
for(int S=0;S<=U;S++)mn=min(mn,calc(gen(S,n)));
for(int S=0;S<=U;S++){
auto a=gen(S,n);
if(calc(a)==mn&&!--k){
for(int i=0;i<::n;i++)printf("%d%c",a[i%6]+1,"\n "[i+1<::n]);
exit(0);
}
}
puts("-1");
}
using big=__int128;
ll pw[N];
ll mul(ll x,ll y){
return min((big)x*y,(big)k);
}
int calc(int i){
if(i==1)return mul(m-1,pw[n-2]);
return pw[n-i];
}
int ans[N];
int main(){
cin>>n>>m>>k;
if(m==1){
if(k>1)return cout<<-1<<endl,0;
for(int i=1;i<=n;i++)printf("1 ");
return cout<<endl,0;
}
if(m==2){
return solve(),0;
}
if(n==1){
if(k>m)return cout<<-1<<endl,0;
return cout<<k<<endl,0;
}
for(int i=pw[0]=1;i<=n;i++)pw[i]=mul(pw[i-1],m-2);
if(mul(m,mul(m-1,pw[n-2]))<k)return cout<<-1<<endl,0;
k--;
for(int i=1;i<=n;i++){
ll base=calc(i);
int cur=k/base+1;
k%=base;
if(i==1)printf("%d ",ans[i]=cur);
else if(i==2){
if(cur<ans[1])printf("%d ",ans[i]=cur);
else printf("%d ",ans[i]=cur+1);
}else{
int x=ans[i-1],y=ans[i-2];
if(x>y)swap(x,y);
if(cur<x)printf("%d ",ans[i]=cur);
else if(cur<y-1)printf("%d ",ans[i]=cur+1);
else printf("%d ",ans[i]=cur+2);
}
}
cout<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3444kb
input:
1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3704kb
input:
2 2 2
output:
2 1
result:
ok 2 number(s): "2 1"
Test #3:
score: 0
Accepted
time: 1ms
memory: 5616kb
input:
3 3 3
output:
2 1 3
result:
ok 3 number(s): "2 1 3"
Test #4:
score: 0
Accepted
time: 1ms
memory: 5656kb
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: 5512kb
input:
10 7 998244353
output:
-1
result:
ok 1 number(s): "-1"
Test #6:
score: 0
Accepted
time: 0ms
memory: 5760kb
input:
3 1000 994253860
output:
998 244 353
result:
ok 3 number(s): "998 244 353"
Test #7:
score: -100
Wrong Answer
time: 1ms
memory: 5636kb
input:
58 4 864691128455135232
output:
2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2
result:
wrong answer 1st numbers differ - expected: '4', found: '2'