QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #200766 | #6353. Kth Lex Min Min Min Subpalindromes | ucup-team870 | AC ✓ | 216ms | 16832kb | C++17 | 3.0kb | 2023-10-04 19:40:11 | 2023-10-04 19:40:11 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=l; i<=r; i++)
#define per(i,r,l) for(int i=r; i>=l; i--)
#define IOS {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);}
#define ilr int i,int l,int r
#define ls i<<1,l,mid
#define rs i<<1|1,mid+1,r
#define mi int mid=l+r>>1;
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
string res[13];
const int N=1e6+6;
int num[N<<2];
void bu(ilr){
num[i]=r-l+1;
if(l==r)return;
mi
bu(ls); bu(rs);
}
void ud(ilr,int x,int v){
num[i]+=v;
if(l==r)return;
mi
if(mid>=x)ud(ls,x,v);
else ud(rs,x,v);
}
int qu(ilr,int k){
if(l==r)return l;
mi
if(num[i<<1]<k)return qu(rs,k-num[i<<1]);
return qu(ls,k);
}
int main() {
IOS
int n,m; ll k;
cin>>n>>m>>k;
// if(n==1){
// if(k>m){
// cout<<-1; return 0;
// }
// cout<<k; return 0;
// }
if(m==1){
if(k>1){
end: cout<<-1; return 0;
}
rep(i,1,n)cout<<1<<' ';
return 0;
}
if(m==2){
int tot=0;
if(0){
end1:
if(k>tot)goto end;
for(auto v:res[k])cout<<v<<' ';
return 0;
}
if(n==1){
tot=2; res[1]="1"; res[2]="2"; goto end1;
}
if(n==2){
tot=2; res[1]="12"; res[2]="21"; goto end1;
}
if(n==3){
tot=6;
res[1]="112"; res[2]="121"; res[3]="122";
res[4]="211"; res[5]="212"; res[6]="221";
goto end1;
}
if(n==4){
tot=10;
res[1]="1121"; res[2]="1122"; res[3]="1211"; res[4]="1212"; res[5]="1221";
res[6]="2112"; res[7]="2121"; res[8]="2122"; res[9]="2211"; res[10]="2212";
goto end1;
}
string s1="121122",s2="212211";
rep(i,0,5){
int x=i; ++tot;
rep(j,1,n)res[tot]+=s1[x],x=(x+1)%6;
}
rep(i,0,5){
int x=i; ++tot;
rep(j,1,n)res[tot]+=s2[x],x=(x+1)%6;
}
sort(res+1,res+tot+1);
goto end1;
}
__int128 all=1;
rep(i,1,n){
if(i==1)all*=m;
else if(i==2)all*=m-1;
else all*=m-2;
if(all>=k)break;
}
if(all<k)goto end;
vector<int> ans(n+1);
auto cal=[&](int x,ll k){
__int128 res=1;
if(m==3){
return (ll)((x==2)?(n==1?1:2):1);
}
rep(i,x,n){
if(i==2)res*=m-1;
else res*=m-2;
if(res>k)return k+1;
}
return (ll)res;
};
bu(1,1,m);
rep(i,1,n){
ll rea=cal(i+1,k);
int v=(k-1)/rea+1; k-=(v-1)*rea;
//!=前2个的第v大
rep(j,1,2){
if(i-j<=0)break;
ud(1,1,m,ans[i-j],-1);
}
ans[i]=qu(1,1,m,v);
// cout<<v<<' ';
rep(j,1,2){
if(i-j<=0)break;
ud(1,1,m,ans[i-j],1);
}
}
rep(i,1,n)cout<<ans[i]<<' ';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3564kb
input:
1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
2 2 2
output:
2 1
result:
ok 2 number(s): "2 1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
3 3 3
output:
2 1 3
result:
ok 3 number(s): "2 1 3"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3800kb
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: 3864kb
input:
10 7 998244353
output:
-1
result:
ok 1 number(s): "-1"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
3 1000 994253860
output:
998 244 353
result:
ok 3 number(s): "998 244 353"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3568kb
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: 3628kb
input:
58 4 864691128455135233
output:
-1
result:
ok 1 number(s): "-1"
Test #9:
score: 0
Accepted
time: 135ms
memory: 16432kb
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: 216ms
memory: 7032kb
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: 3600kb
input:
1 1 2
output:
-1
result:
ok 1 number(s): "-1"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3832kb
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: 0
Accepted
time: 0ms
memory: 3580kb
input:
3 2 4
output:
2 1 1
result:
ok 3 number(s): "2 1 1"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
3 2 7
output:
-1
result:
ok 1 number(s): "-1"
Test #16:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
4 2 10
output:
2 2 1 2
result:
ok 4 number(s): "2 2 1 2"
Test #17:
score: 0
Accepted
time: 0ms
memory: 3520kb
input:
4 2 3
output:
1 2 1 1
result:
ok 4 number(s): "1 2 1 1"
Test #18:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
5 2 7
output:
2 1 1 2 1
result:
ok 5 number(s): "2 1 1 2 1"
Test #19:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
5 2 13
output:
-1
result:
ok 1 number(s): "-1"
Test #20:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
6 2 5
output:
1 2 2 1 1 2
result:
ok 6 numbers
Test #21:
score: 0
Accepted
time: 51ms
memory: 16832kb
input:
1000000 2 3
output:
1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 ...
result:
ok 1000000 numbers
Test #22:
score: 0
Accepted
time: 60ms
memory: 16832kb
input:
1000000 2 5
output:
1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 ...
result:
ok 1000000 numbers
Test #23:
score: 0
Accepted
time: 56ms
memory: 16800kb
input:
1000000 2 7
output:
2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 ...
result:
ok 1000000 numbers
Test #24:
score: 0
Accepted
time: 28ms
memory: 16768kb
input:
1000000 2 1000000000000000000
output:
-1
result:
ok 1 number(s): "-1"
Test #25:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
1 3 2
output:
2
result:
ok 1 number(s): "2"
Test #26:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
2 3 5
output:
3 1
result:
ok 2 number(s): "3 1"
Test #27:
score: 0
Accepted
time: 46ms
memory: 6956kb
input:
1000000 3 5
output:
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 1 2 ...
result:
ok 1000000 numbers
Test #28:
score: 0
Accepted
time: 2ms
memory: 3576kb
input:
1000000 3 7
output:
-1
result:
ok 1 number(s): "-1"
Test #29:
score: 0
Accepted
time: 182ms
memory: 6996kb
input:
1000000 4 211106232532991
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 #30:
score: 0
Accepted
time: 146ms
memory: 6980kb
input:
1000000 5 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 #31:
score: 0
Accepted
time: 115ms
memory: 8028kb
input:
1000000 123123 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 #32:
score: 0
Accepted
time: 5ms
memory: 13320kb
input:
6 1000000 1000000000000000000
output:
1 2 4 9 15 8
result:
ok 6 numbers
Test #33:
score: 0
Accepted
time: 5ms
memory: 12820kb
input:
4 1000000 1000000000000000000
output:
2 7 15 9
result:
ok 4 number(s): "2 7 15 9"
Test #34:
score: 0
Accepted
time: 0ms
memory: 12108kb
input:
3 1000000 999997000002000000
output:
1000000 999999 999998
result:
ok 3 number(s): "1000000 999999 999998"
Test #35:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
3 1000000 999997000002000001
output:
-1
result:
ok 1 number(s): "-1"