QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#425021 | #6353. Kth Lex Min Min Min Subpalindromes | ushg8877 | WA | 1ms | 11428kb | C++14 | 1.5kb | 2024-05-29 21:23:22 | 2024-05-29 21:23:23 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define LL __int128
const int MAXN=1e6+5;
ll n,m,k;
LL pw(LL a,int b){LL r=1;while(b){if(b&1)r=min(r*a,(LL)k+1);a=min(a*a,(LL)k+1),b>>=1;}return min(r,(LL)k+1);}
int ans[MAXN],b[MAXN];
bool check(int x){
if(x>=3&&b[x-2]==b[x-1]&&b[x-1]==b[x]) return false;
if(x>=5&&b[x-3]==b[x-1]&&b[x-4]==b[x]) return false;
if(x>=6&&b[x-5]==b[x]&&b[x-4]==b[x-1]&&b[x-3]==b[x-2]) return false;
return true;
}
void dfs(int u){
if(!k) return;
if(u==n+1){
if(--k==0) swap(ans,b);
return;
}
for(int o:{1,2}){
b[u]=o;
if(check(u)){
dfs(u+1);
if(!k) return;
}
}
}
int main(){
ios::sync_with_stdio(false);
// freopen("Otomachi_Una.in","r",stdin);
// freopen("Otomachi_una.out","w",stdout);
cin>>n>>m>>k;
if(n==1){
if(k<=m) cout<<k;
else cout<<"-1";
return 0;
}
if(m==1){
if(k==1){
for(int i=1;i<=n;i++) cout<<"1 ";
}else cout<<"-1";
}else if(m>=3){
for(int x=1;x<=m;x++){
if(k>(m-1)*pw(m-2,n-2)) k-=(m-1)*pw(m-2,n-2);
else{
ans[1]=x;
break;
}
}
if(!ans[1]) cout<<"-1";
else{
for(int i=2;i<=n;i++){
for(int j=1;j<=m;j++)if(j!=ans[i-1]&&j!=ans[i-2]){
if(k>pw(m-2,n-i)) k-=pw(m-2,n-i);
else{
ans[i]=j;
break;
}
}
}
for(int i=1;i<=n;i++) cout<<ans[i]<<' ';
}
}else{
// hard one :(, I think that has no 111 and 000 and any 5/6- palind in it?
dfs(1);
if(k) cout<<"-1";
else{
for(int i=1;i<=n;i++) cout<<ans[i]<<' ';
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3744kb
input:
1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 11428kb
input:
2 2 2
output:
1 2
result:
wrong answer 1st numbers differ - expected: '2', found: '1'