QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #103597 | #6353. Kth Lex Min Min Min Subpalindromes | sergiomacario# | WA | 80ms | 3608kb | C++14 | 2.0kb | 2023-05-07 00:26:32 | 2023-05-07 00:26:35 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m;
ll k;
string s[12] = {"112122", "112212", "121122", "121221", "122112", "122121", "211212", "211221", "212112", "212211", "221121", "221211"};
int main(){
scanf("%d %d %lld", &n, &m, &k);
if(m == 1){
if(k == 1)
for(int i = 0; i < n; i++)
printf("1 ");
else
printf("-1\n");
}
else if(m == 2){
if(n == 1){
if(k <= 2)
printf("%lld\n", k);
else
printf("-1\n");
}
else if(n == 2){
if(k <= 2)
printf("%lld %lld\n", k, 3 - k);
else
printf("-1\n");
}
else if(n == 3){
if(k <= 6)
printf("%c %c %c\n", s[2 * k - 1][0], s[2 * k - 1][1], s[2 * k - 1][2]);
else
printf("-1\n");
}
else{
if(k <= 12)
for(int i = 0; i < n; i++)
printf("%c ", s[k - 1][i % 6]);
else
printf("-1\n");
}
}
else{
ll tot = m;
if(n > 1)
tot *= m - 1;
int h = 3;
while(h <= n && tot <= k / (m - 2)){
tot *= m - 2;
h++;
}
if(tot < k && h > n)
printf("-1\n");
else{
int ant = m + 1, ant2 = m + 1;
for(int i = 1; i <= n; i++){
if(i == 1)
tot /= m;
else if(i == 2)
tot /= (m - 1);
else{
if(h <= i)
h++;
else
tot /= (m - 2);
}
while(h <= n && tot <= k / (m - 2)){
tot *= m - 2;
h++;
}
int hh;
if(h <= n){
hh = 1;
if(ant <= hh){
hh++;
if(ant2 <= hh)
hh++;
}
else if(ant2 <= hh){
hh++;
if(ant <= hh)
hh++;
}
printf("%lld ", hh);
}
else{
hh = (k - 1) / tot + 1;
k -= (hh - 1) * tot;
if(ant <= hh){
hh++;
if(ant2 <= hh)
hh++;
}
else if(ant2 <= hh){
hh++;
if(ant <= hh)
hh++;
}
printf("%lld ", hh);
}
ant2 = ant;
ant = hh;
//cout << h << " " << k << " " << tot << endl;
}
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3608kb
input:
1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 2ms
memory: 3604kb
input:
2 2 2
output:
2 1
result:
ok 2 number(s): "2 1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
3 3 3
output:
2 1 3
result:
ok 3 number(s): "2 1 3"
Test #4:
score: 0
Accepted
time: 2ms
memory: 3604kb
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: 3596kb
input:
10 7 998244353
output:
-1
result:
ok 1 number(s): "-1"
Test #6:
score: 0
Accepted
time: 2ms
memory: 3608kb
input:
3 1000 994253860
output:
998 244 353
result:
ok 3 number(s): "998 244 353"
Test #7:
score: 0
Accepted
time: 1ms
memory: 3592kb
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: 2ms
memory: 3520kb
input:
58 4 864691128455135233
output:
-1
result:
ok 1 number(s): "-1"
Test #9:
score: 0
Accepted
time: 77ms
memory: 3592kb
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: 80ms
memory: 3604kb
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: 2ms
memory: 3588kb
input:
1 1 2
output:
-1
result:
ok 1 number(s): "-1"
Test #12:
score: 0
Accepted
time: 2ms
memory: 3588kb
input:
1 2 2
output:
2
result:
ok 1 number(s): "2"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
2 2 1
output:
1 2
result:
ok 2 number(s): "1 2"
Test #14:
score: 0
Accepted
time: 1ms
memory: 3524kb
input:
3 2 4
output:
2 1 1
result:
ok 3 number(s): "2 1 1"
Test #15:
score: 0
Accepted
time: 2ms
memory: 3552kb
input:
3 2 7
output:
-1
result:
ok 1 number(s): "-1"
Test #16:
score: -100
Wrong Answer
time: 2ms
memory: 3608kb
input:
4 2 10
output:
2 1 2 2
result:
wrong answer 2nd numbers differ - expected: '2', found: '1'