QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#487345#6353. Kth Lex Min Min Min Subpalindromesucup-team2307#AC ✓47ms24744kbC++202.5kb2024-07-22 20:18:062024-07-22 20:18:09

Judging History

你现在查看的是最新测评结果

  • [2024-07-22 20:18:09]
  • 评测
  • 测评结果:AC
  • 用时:47ms
  • 内存:24744kb
  • [2024-07-22 20:18:06]
  • 提交

answer

#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
#pragma GCC target("avx,avx2,sse,sse2")
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
#define int ll


int n,m,k;

vector<int> cur;
int best=1e18;
vector<vector<int>> ans;

bool check(int l,int r)
{
    for(int i=l,j=r;i<j;i++,j--)
        if(cur[i]!=cur[j])
            return false;
    return true;
}

int calc()
{
    int res=0;
    for(int l=0;l<n;l++)
        for(int r=l;r<n;r++)
            res+=check(l,r);
    return res;
}

void brute()
{
    if(cur.size()==n){
        int cnt=calc();
        if(cnt<best)
            best=cnt,
                    ans={cur};
        else if(cnt==best)
            ans.push_back(cur);
        return;
    }
    cur.push_back(-1);
    for(int i=1;i<=m;i++)
    {
        cur.back()=i;
        brute();
    }
    cur.pop_back();
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    // for(int n = 1; n <= 25; n++) {
    // 	int x = n, y = 0;
    // 	for(int msk = 0; msk < 1<<n; msk++)
    // 		x = min(x, longest(n, msk));
    // 	for(int msk = 0; msk < 1<<n; msk++)
    // 		y += longest(n, msk) == x;
    // 	cout << n << " : " << x << " " << y << endl;
    // }
    cin >> n >> m >> k;
    if(m == 1) {
        if(k > 1) cout << "-1\n";
        else for(int i = 0; i < n; i++) cout << "1 ";
        return 0;
    }
    k--;
    if(m == 2) {
        int my_n=n;
        n=min<int>(n,12);
        brute();
        if(k>=ans.size())
            cout<<-1;
        else
        {
            for(int i=0;i<my_n;i++)
                cout<<ans[k][i%ans[k].size()]<<" ";
        }
        return 0;
    }
#undef int
    const __int128 inf = ll(1e18) + 44;
    vector<__int128> suf_ways(n + 1);
    suf_ways[0] = 1;
    for(int i = 1; i <= n; i++) {
        if(i == n) suf_ways[i] = min(suf_ways[i - 1] * m, inf);
        else if(i + 1 == n) suf_ways[i] = min(suf_ways[i - 1] * (m - 1), inf);
        else suf_ways[i] = min(suf_ways[i - 1] * (m - 2), inf);
    }
    if(k >= suf_ways.back()) {
        cout << "-1\n";
        return 0;
    }
    ll p2 = m + 1, p1 = m + 1;
    vector<int> ans;
    for(int i = 0; i < n; i++) {
        ll ord = k / suf_ways[n - 1 - i] + 1;
        ll val = ord;
        while(val == p1 || val == p2 || (val - (p1<val) - (p2<val)) < ord) val++;
        p2 = exchange(p1, val);
        ans.push_back(val);

        k %= suf_ways[n - 1 - i];
    }
    for(auto i : ans) cout << i << ' '; cout << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3572kb

input:

1 1 1

output:

1 

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3512kb

input:

2 2 2

output:

2 1 

result:

ok 2 number(s): "2 1"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3792kb

input:

3 3 3

output:

2 1 3 

result:

ok 3 number(s): "2 1 3"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3560kb

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: 3568kb

input:

10 7 998244353

output:

-1

result:

ok 1 number(s): "-1"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3556kb

input:

3 1000 994253860

output:

998 244 353 

result:

ok 3 number(s): "998 244 353"

Test #7:

score: 0
Accepted
time: 0ms
memory: 3628kb

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: 3792kb

input:

58 4 864691128455135233

output:

-1

result:

ok 1 number(s): "-1"

Test #9:

score: 0
Accepted
time: 47ms
memory: 24744kb

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: 40ms
memory: 23188kb

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: 3564kb

input:

1 1 2

output:

-1

result:

ok 1 number(s): "-1"

Test #12:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

1 2 2

output:

2 

result:

ok 1 number(s): "2"

Test #13:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

2 2 1

output:

1 2 

result:

ok 2 number(s): "1 2"

Test #14:

score: 0
Accepted
time: 0ms
memory: 3868kb

input:

3 2 4

output:

2 1 1 

result:

ok 3 number(s): "2 1 1"

Test #15:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

3 2 7

output:

-1

result:

ok 1 number(s): "-1"

Test #16:

score: 0
Accepted
time: 0ms
memory: 3872kb

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: 3564kb

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: 3628kb

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: 3620kb

input:

5 2 13

output:

-1

result:

ok 1 number(s): "-1"

Test #20:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

6 2 5

output:

1 2 2 1 1 2 

result:

ok 6 numbers

Test #21:

score: 0
Accepted
time: 41ms
memory: 3628kb

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: 40ms
memory: 3632kb

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: 36ms
memory: 3628kb

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: 2ms
memory: 3600kb

input:

1000000 2 1000000000000000000

output:

-1

result:

ok 1 number(s): "-1"

Test #25:

score: 0
Accepted
time: 0ms
memory: 3872kb

input:

1 3 2

output:

2 

result:

ok 1 number(s): "2"

Test #26:

score: 0
Accepted
time: 0ms
memory: 3572kb

input:

2 3 5

output:

3 1 

result:

ok 2 number(s): "3 1"

Test #27:

score: 0
Accepted
time: 38ms
memory: 23884kb

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: 3ms
memory: 18740kb

input:

1000000 3 7

output:

-1

result:

ok 1 number(s): "-1"

Test #29:

score: 0
Accepted
time: 47ms
memory: 24444kb

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: 35ms
memory: 23540kb

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: 47ms
memory: 23104kb

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: 0ms
memory: 3528kb

input:

6 1000000 1000000000000000000

output:

1 2 4 9 15 8 

result:

ok 6 numbers

Test #33:

score: 0
Accepted
time: 0ms
memory: 3628kb

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: 3560kb

input:

3 1000000 999997000002000000

output:

1000000 999999 999998 

result:

ok 3 number(s): "1000000 999999 999998"

Test #35:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

3 1000000 999997000002000001

output:

-1

result:

ok 1 number(s): "-1"