QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#460947 | #6353. Kth Lex Min Min Min Subpalindromes | grass8cow# | WA | 50ms | 15756kb | C++17 | 1.9kb | 2024-07-02 14:06:03 | 2024-07-02 14:06:04 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int a[1010000],oo;
vector<int>vp;
vector<int>brute(int n){
oo=1e9;
for(int s=0;s<(1<<n);s++){
for(int i=1;i<=n;i++)a[i]=((s>>(i-1))&1)+1;
int an=0;
for(int i=1;i<=n;i++){
int d=0;
while(a[i-d]==a[i+d])d++;
an+=d;
}
for(int i=1;i<n;i++){
int d=0;
while(a[i-d]==a[i+1+d])d++;
an+=d;
}
if(an>oo)continue;
if(oo>an)oo=an,vp.clear();
vp.push_back(s);
}
return vp;
}
#define ll long long
const ll I=1e18+10;
int n,m;ll k,e[1010000];
int main(){
scanf("%d%d%lld",&n,&m,&k);
if(m==1){
if(k>1)puts("-1");
else{for(int i=1;i<=n;i++)printf("1 ");}
return 0;
}
if(m>=3){
e[n+1]=1;
for(int i=n;i;i--){
int z=m-min(i,3)+1;
if(e[i+1]<=I/z)e[i]=e[i+1]*z;
else e[i]=I;
}
if(k>e[1]){puts("-1");return 0;}
for(int i=1;i<=n;i++){
int z=(k-1)/e[i+1]+1;
k-=(z-1)*e[i+1];
if(i==2&&z>=a[i-1])z++;
if(i>2){
int x=a[i-2],y=a[i-1];if(x>y)swap(x,y);
if(z>=x)z++;if(z>=y)z++;
}
a[i]=z;
printf("%d ",a[i]);
}
return 0;
}
if(n<=5){
vector<int>aa=brute(n);
sort(aa.begin(),aa.end());
if(aa.size()<k){puts("-1");return 0;}
int e=aa[k-1];
for(int i=n-1;i>=0;i--)printf("%d ",((e>>i)&1)+1);
return 0;
}
vector<int>aa=brute(5);
sort(aa.begin(),aa.end());
if(aa.size()<k){puts("-1");return 0;}
int e=aa[k-1];
for(int i=4;i>=0;i--)a[5-i]=((e>>i)&1);
for(int i=6;i<=n;i++){
if(a[i-2]==a[i-1])a[i]=a[i-3];
else if(a[i-1]==a[i-3])a[i]=a[i-4]^1;
else a[i]=a[i-5]^1;
}
for(int i=1;i<=n;i++)printf("%d ",a[i]+1);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3796kb
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: 3712kb
input:
3 3 3
output:
2 1 3
result:
ok 3 number(s): "2 1 3"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3716kb
input:
9 9 8244353
output:
2 4 1 2 6 8 1 2 7
result:
ok 9 numbers
Test #5:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
10 7 998244353
output:
-1
result:
ok 1 number(s): "-1"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3892kb
input:
3 1000 994253860
output:
998 244 353
result:
ok 3 number(s): "998 244 353"
Test #7:
score: 0
Accepted
time: 1ms
memory: 3844kb
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: 0ms
memory: 3600kb
input:
58 4 864691128455135233
output:
-1
result:
ok 1 number(s): "-1"
Test #9:
score: 0
Accepted
time: 50ms
memory: 15756kb
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: 38ms
memory: 15744kb
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: 1ms
memory: 3600kb
input:
1 1 2
output:
-1
result:
ok 1 number(s): "-1"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
1 2 2
output:
2
result:
ok 1 number(s): "2"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
2 2 1
output:
1 2
result:
ok 2 number(s): "1 2"
Test #14:
score: -100
Wrong Answer
time: 0ms
memory: 3756kb
input:
3 2 4
output:
2 2 1
result:
wrong answer 2nd numbers differ - expected: '1', found: '2'